1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 5; int n, m, dfn[maxn], low[maxn], idx, dcc, id[maxn]; stack<int> stk; vector<int> g[maxn], G[maxn]; void tarjan(int u, int p) { dfn[u] = low[u] = ++idx; stk.push(u); for (auto v : g[u]) { if (v == p) continue; if (!dfn[v]) tarjan(v, u), low[u] = min(low[u], low[v]); else low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]) { dcc++; int v; do { v = stk.top(); stk.pop(); id[v] = dcc; } while (v != u); } } void build_new_grapph() { set<pair<int, int>> st; for (int u = 1; u <= n; u++) { for (auto v : g[u]) { int uu = id[u], vv = id[v]; if (uu != vv && !st.count({uu, vv})) { st.insert({uu, vv}); st.insert({vv, uu}); G[uu].push_back(vv); G[vv].push_back(uu); } } } } int dis[maxn]; void dfs(int u, int p, int d) { dis[u] = d; for (auto v : G[u]) if (v != p) dfs(v, u, d+1); } int main() { scanf("%d%d", &n, &m); while (m--) { int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } tarjan(1, -1); // test(); build_new_grapph(); dfs(1, -1, 0); int p = 1; for (int i = 1; i <= dcc; i++) if (dis[i] > dis[p]) p = i; // test2(); dfs(p, -1, 0); int ans = 0; for (int i = 1; i <= dcc; i++) ans = max(ans, dis[i]); // test2(); printf("%d\n", ans); return 0; }
- 1
信息
- ID
- 70
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 8
- 已通过
- 2
- 上传者