Tarjan(割点) - Electricity - POJ 2117

题意：

给定一个由 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

---

分析：

$目标即在所有连通分量中选择一个割点，使得删除该点后分出的连通块数量最多。$

如何判断割点：

$条件：dfn[u]≤low[j]。$

$①、若u不是根节点，删除u以后，u的父节点所在连通块与孩子节点所在连通块将分成多个部分。此时u是割点。$

$情况①如下图：$

$删除u后，会分成1，2，3三个连通分量。$

$②、若u是根节点，那么u至少有两个孩子，才能确保u是割点。若u仅有一个孩子，删去u后，连通分量数量不增加。$

$情况②如下图：$

对条件的说明：

$dfn[u]≤low[j]。$

$等号是可以取的。取等时u与j或j的孩子之间形成环，删去u仍然会与j分开。$

$dfn][u]>low[j]时，即u在环的内部，删去u就不能够增加连通分量的数量。$

具体步骤：

$这样我们对于连通块中的每个点u，统计满足dfn[u]≤low[j]的孩子j的数量。$

$有一个j，就能够多分出一个孩子连通分量。$

$注意，若u不是根节点，最后还需要增加一个父节点所在的连通分量。$

$用全局变量ans来更新去除每个点能够分出的连通块数量的最大值。$

$记连通块总数初始为cnt，最大答案为ans+(cnt-1)。$

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;const int N=10010, M=30010;int n,m;
int e[M],ne[M],h[N],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 res=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]) res++;}else low[u]=min(low[u],dfn[j]);}if(u!=root) res++;ans=max(ans,res);
}int main()
{while(~scanf("%d%d",&n,&m),n||m){memset(h,-1,sizeof h);memset(dfn,0,sizeof dfn);idx=0,ans=0,timestamp=0;int a,b;for(int i=0;i<m;i++){scanf("%d%d",&a,&b);add(a,b),add(b,a);}int cnt=0;  //统计有多少连通分量for(root=0;root<n;root++)if(!dfn[root]){tarjan(root);cnt++;}printf("%d\n",ans+cnt-1);}return 0;
}