目录
题目描述
原题来自：CTU Open 2004
求一个图删除一个点之后，联通块最多有多少。
输入格式
多组数据。第一行两个整数 表示点数和边数。
接下来 行每行两个整数 ，表示 与 有边连接，保证无重边。读入以 0 0 结束。
输出格式
输出若干行，表示每组数据的结果。
样例
样例输入
3 3
0 1
0 2
2 1
4 2
0 1
2 3
3 1
1 0
0 0
样例输出
1
2
2
数据范围与提示
$ 1 \le P \le 10000,C \ge 0,0 \le p1, p2 < P $
$ solution $
回想我们判断割点时的条件
- $ 1° $ 搜索树 子树中存在点 $ low[v] >= dfn[u] $，即返回的时间戳不小于当前点u，删除这个点u，子树分离
- $ 2° $ 根节点 一个根节点root 满足超过两棵子树即为割点，很好理解
回到此题 - 对于情况一。当前点u，每有一个满足的子树，删除点u后就会有一个联通块，记录个数即可；
此外，还需要考虑点u的父亲，删除割点u后他的父亲与他的子树们也会分裂，个数++ - 对于情况二。好办，子树的个数
这样下来就得到了每个点删除后形成的新联通块个数
由于此题图不一定联通，所以我们有这句话
for(int i = 1; i <= n; i++) if(!dfn[i]) ans ++, tarjan(i, i);
每断开一个点，原联通块消失，分裂成几部分，这也就是答案统计
代码好看
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+50;
struct node{ int next, to; } edge[N<<1];
int head[N], cnt;
inline void add(int from, int to) { edge[++cnt] = (node) {head[from], to}, head[from] = cnt; }
int tot, low[N], dfn[N], cut[N];
void tarjan(int u, int fa) {
low[u] = dfn[u] = ++tot; int child = 0;
for(int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if(!dfn[v]) {
tarjan(v, fa), low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u] && u != fa) cut[u] ++;
if(u == fa) child ++;
}
else low[u] = min(low[u], dfn[v]);
}
if(u != fa && cut[u]) cut[u] ++;//fa 所构成的一块
if(u == fa && child >= 2) cut[u] += child ;
}
int main() {
while(1) {
#define clear(a) memset(a, 0, sizeof a)
int n, m; cin>>n>>m;
if(n + m == 0) break;
if(m == 0) { printf("%d\n", n - 1); continue; }
clear(low), clear(cut), clear(dfn),clear(head),clear(edge);
cnt = tot = 0;
for(int i = 1, a, b; i <= m; i++) scanf("%d%d", &a, &b), add(++a, ++b), add(b, a);
int ans = 0;
for(int i = 1; i <= n; i++) if(!dfn[i]) ans ++, tarjan(i, i);
int temp = ans;
for(int i = 1; i <= n; i++) ans = max(ans, temp - 1 + cut[i]);
printf("%d\n", ans);
}
return 0;
}