题目描述
给定一个由 n 个点 m 条边构成的无向图,请你求出该图删除一个点之后,连通块最多有多少。
输入格式
输入包含多组数据。
每组数据第一行包含两个整数 n,m。
接下来 m 行,每行包含两个整数 a,b,表示 a,b 两点之间有边连接。
数据保证无重边。
点的编号从 0 到 n−1。
读入以一行 0 0 结束。
输出格式
每组数据输出一个结果,占一行,表示连通块的最大数量。
数据范围
1≤n≤10000,
0≤m≤15000,
0≤a,b<n
样例
3 3
0 1
0 2
2 1
4 2
0 1
2 3
3 1
1 0
0 0
1
2
2
算法1
(tarjan求割点) $O(n + m)$
本题算法步骤:
1、统计连通块个数 cnt
2、枚举从哪个连通块中删,删哪个割点,删除割点之后的连通块个数是多少? 用 ans 记录一个全局最大值
3、答案就是 ans + cnt - 1
如何求割点?
x -> y low[y] >= dfn[x] x是割点,y是一个连通块
对于low[y] >= dfn[x] 有两种情况
1、x不是根结点,删除后就会使得连通块不连通
2、x是根结点,至少得有两个子树,否则删除x,连通块仍然是连通的。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010,M = 30010;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int root,ans;
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]);
}
// 当执行到这行代码时,意味着当前节点u的所有邻边都已经遍历完了
// cnt 不为 0,意味着这是个割点,u != root 那么删除割点后的连通块个数要加1,加上当前结点u的父连通块
if(u != root && cnt) cnt ++;
ans = max(ans,cnt); // ans 记录的是枚举每个连通块中删除每个割点所得到连通块的最大值
}
int main()
{
while(scanf("%d%d",&n,&m),n || m){
memset(dfn,0,sizeof dfn);
memset(h, -1, sizeof h);
idx = 0;
while(m -- ){
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
ans = 0;
int cnt = 0; // 统计连通块个数
// root 表示每个连通块的根节点
for(root = 0;root < n;root++){
if(!dfn[root]){
cnt ++; // 连通块个数 + 1
tarjan(root);
}
}
printf("%d\n",ans + cnt - 1);
}
return 0;
}
哇,666