題目

分析

這是割點的板子?

代碼

#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);}
}