链接：http://poj.org/problem?id=1523
题意：N台电脑，如果某台坏掉了，其他电脑就会分成几个不相连接的部分。找出这些电脑，并且算出其坏了其他电脑会分成几个部分。
思路：Tarjan算法求割点。模板来源自刘汝佳白书。
相关资料：（以下转载，源头不可考）
无向连通图的割点与割边：
最简单的方法：要判断一个点是否为割点，先把这个点和所有和它连接的边从图中去掉，再遍历下剩余的图，看看是否为连通的即可。这只在单独判断某一点(边)时才会选用。
时间复杂度O(n2)。
割点将一个图分成了两部分，设从任一部分的任一点出发对图进行DFS遍历，当遍历递归到割点后，就进入了图的第二部分。又因为每个点只能visit一次，所以第二部分的点不论怎样遍历再也回不到第一部分了。当所有点(第二部分中)都被访问完后，才回溯到割点，再继续向上回溯。
在DFS的过程中，记录每个点u在DFS树中的标号n1(放在dep[u]中)，以及该点所能到达的最小顺序号n2(存在low[u]中)。注意：这个n2在求取时，是递归进行的，从u的子孙们的low值n2与u的祖先们的dep值n1(此时u祖先的low值还未求出，dep相当于它的low值)中挑出最小的。这就给了u的儿子们low值比u还小的机会。然而，如果u是割点，那么u孩子们的low值就决然 >= u 了。这也就成了判断u是割点的方法。
至于割边，可以再判断u是否为割点的同时，顺便判断<u,u儿子i>是否为割边。只要满足low[i]>u就行了。
另外，对于dfs起点就是一个割点的情况：如果不是割点，那它必然只有一个儿子(其他连接都被dfs回溯掉了)。它必须是割点，才能保证它的几个儿子不被dfs回溯掉。
注意：想要记录割点u切去后增加的连通分量数目。不能简单的记录u的孩子数，而必须在判断u为割点成立的地方进行统计。即有多少个证明了u是割点的孩子，它们就是u在切除后生成的新连通分量。割点u的某些孩子不一定能证明u是割点，因为它可能与比u小的某个点相连，从而使自己的low值比u还小，这与具体的dfs树有关，即遍历的顺序有关。 可见末尾的一组数据，对同一个图的描述，由于建树的方式不同，导致3的儿子4，不能证明3是割点。从而使3的孩子数(3) ！= 3造就的连通分量数2（删除3后，两棵子树成为连通分量）。
针对这点再强调一点：对根节点删掉自己后，就只剩新生的联通分量了。不同于枝节点，还有旧的连通分量在。
汇总如下：
如果根结点有大于1个的儿子，那么根结点是割点。
如果对于点u的某个儿子v，有low[v] >= dep[u]，那么u就是一个割点。
如果对于点u的某个儿子v，有low[v] > dep[u]，那么(u,v)是一条割边。
（转载结束）
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <ctype.h>
#include <algorithm>
#include <string>
#define PI acos(-1.0)
#define maxn 1005
#define INF 1<<25
#define MAX 0x7fffffff
#define mem(a,b) memset(a,b,sizeof(a))
#define f(i,a,b) for(i=a;i<b;i++)
typedef long long ll;
using namespace std;
struct Edge
{
int v;
int next;
} edge[maxn];
int head[maxn],pre[maxn],iscut[maxn],low[maxn];
int top=0,dfs_clock=0,a,b,T,ans,i,ii=0;
bool jud;
int add_edge(int u,int v)
{
edge[top].v=v;
edge[top].next=head[u];
head[u]=top++;
edge[top].v=u;
edge[top].next=head[v];
head[v]=top++;
}
int dfs(int u,int fa)
{
int lowu=pre[u]=++dfs_clock;
int child=0;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].v;
if(!pre[v])
{
child++;
int lowv=dfs(v,u);
lowu=min(lowu,lowv);
if(lowv>=pre[u])
iscut[u]++;
}
else if(pre[v]<pre[u]&&v!=fa)
{
lowu=min(lowu,pre[v]);
}
}
if(fa<1&&child==1)
iscut[u]=0;
low[u]=lowu;
return lowu;
}
int init()
{
mem(iscut,0);
mem(pre,0);
mem(head,-1);
mem(edge,0);
mem(low,0);
top=0;
dfs_clock=0;
T=0;
ans=0;
jud=0;
}
int main()
{
while(scanf("%d",&a))
{
if(!a)
break;
ii++;
init();
scanf("%d",&b);
add_edge(a,b);
if(a>T)
T=a;
if(b>T)
T=b;
while(scanf("%d",&a))
{
if(!a)
break;
scanf("%d",&b);
add_edge(a,b);
if(a>T)
T=a;
if(b>T)
T=b;
}
dfs(1,0);
printf("Network #%d\n",ii);
f(i,1,T)
{
if(i==1)
{
if(iscut[i]>1)
{
printf(" SPF node %d leaves %d subnets\n",i,iscut[i]);
jud=1;
}
}
else if(iscut[i])
{
jud=1;
printf(" SPF node %d leaves %d subnets\n",i,iscut[i]+1);
}
}
if(!jud)
puts(" No SPF nodes");
puts("");
}
}
原文：http://blog.csdn.net/ooooooooe/article/details/19845361