【电力——tarjan割点，求连通块】

题目

分析

这是割点的板子 

代码 #include <bits/stdc++.h> using namespace std; const int N = 1e4+10; const int M = 3e4+10; int h[N], e[M], ne[M], idx; int dfn[N], low[N], tot; int root, ans; void add(int a, int b) // 添加一条边a->b { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } void tarjan(int u) { dfn[u] = low[u] = ++tot; int cnt = 0; for(int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if(!dfn[j]) { tarjan(j); low[u] = min(low[u], low[j]); if(low[j] >= dfn[u]) cnt++; } else low[u] = min(low[u], dfn[j]); } if(u != root) cnt++; ans = max(ans, cnt); } int main() { int n, m; while(scanf("%d%d", &n, &m), n || m) { idx = tot = 0; memset(h, -1, sizeof h); memset(dfn, 0, sizeof dfn); for(int i = 1; i <= m; i++) { int a, b; scanf("%d%d", &a, &b); add(a, b), add(b, a); } ans = 0; //删掉结点的最大贡献 int cnt = 0; //连通块数目 for(root = 0; root < n; root++) if(!dfn[root]) tarjan(root), cnt++; printf("%d\n", cnt + ans - 1); } }