poj 1523Tarjan算法的含义——求取割点可以分出的连通分量的个数
题目大意:如题目所示
给你一些关系图——连通图，想要问你有没有个节点，损坏后，可以生成几个互相独立的网络（也就是连通分量），所以我们利用tarjan算法，求取一个联通分量的点，记录次数，因为访问几次，就代表这个点的不同方向上的联通分量的个数，记录下来，最后输出即可
至于根节点的选取，选谁都没什么问题的，我默认选的节点1
嗯，没什么了，tarjan算法到这算是入门啦
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxn = 1e3 + 10;
struct node{
int to,pre;
}e[maxn * 2];
int id[maxn],cnt;
int index;
int root;
int dfn[maxn],low[maxn];
int subnets[maxn];
int flag;
int p_cnt;
void init()
{
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(subnets,0,sizeof(subnets));
memset(id,-1,sizeof(id));
index = 0;
flag = 0;
cnt = 0;
p_cnt = 0;
}
void add(int u,int v)
{
e[cnt].to = v;
e[cnt].pre = id[u];
id[u] = cnt++;
p_cnt = max(max(u,v),p_cnt);
} void tarjan(int u,int pre)
{
int son = 0;
dfn[u] = low[u] = ++index;
for(int i = id[u];~i;i = e[i].pre)
{
int v = e[i].to;
if(!dfn[v])
{
tarjan(v,u);
son++;
low[u] = min(low[v],low[u]); if(u == root && son > 1)
{
flag = 1;
subnets[u]++;//发现一个
}
if(u != root && low[v] >= dfn[u])
{
subnets[u]++;//发现一个连通分量
flag = 1;
}
}
else if(v != pre)
{
low[u] = min(low[u],dfn[v]);
}
}
}
int main()
{
int cas = 0;
while(true)
{
int u,v = -1;
init();
while(scanf("%d",&u),u)
{
scanf("%d",&v);
add(u,v);
add(v,u);
}
if(v == -1)break;
root = 1;
tarjan(root,-1); printf("Network #%d\n",++cas);
if(flag)
{
for(int i = 1;i <= p_cnt;i++)
{
if(subnets[i] > 0)
{
printf(" SPF node %d leaves %d subnets\n",i,subnets[i]+1);//加上fa->u该边所连接的连通分量
}
}
}
else
{
printf(" No SPF nodes\n");
}
printf("\n");
}
return 0;
}