无向图的双连通分量
点的双连通分量 求割点
#include <bits/stdc++.h>
using namespace std;
const int N = 10010, M = 3e4 + 10;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int root, ans;
int n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
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(cnt, ans);
}
int main(void)
{
while (scanf("%d%d", &n, &m), n || m)
{
memset(h, -1, sizeof h);
memset(dfn, 0, sizeof dfn);
idx = timestamp = 0;
ans = 0;
for (int i = 0; i < m; i ++)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
int cnt = 0;
for (root = 0; root < n; root ++)
if (!dfn[root])
{
cnt ++;
tarjan(root);
}
//cnt - 1 是在一个连通块当中取了一个点
cout << ans + cnt - 1 << endl;
}
return 0;
}