图的割点tarjan---zoj_1119

       http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1119

       如果将连通图G中的某个点及和这个点相关的边删除后，将使原图不再连通，那么这个点就称为图G的割点或是接合点。如果一个无向图没有割点，则这样的图被称为双连通图。

      算法用到了一下两个数组。

      dfn：这个点在dfs序列中的位置

      low：经过这个点及这个点的所有儿子能追溯到的dfn最小点的dfn值~~

     这样我们发现，如果发现low(儿子)>=dfn(父亲)，那么这个父亲就是一个割点。（他的儿子向下找没法重新找到自己的父亲~）

      当然这还是不够的，我们发现对于我们搜索的第一个点来说，他的dfn值是1，永远不会有点的low值比他大，所以我们要特判下，如果说他的真正的儿子（就是dfs的时候找到的儿子，也就是环不算）的个数大于1的话，他就是一个割点。

zoj_1119

#include <cstring> 
#include <cstdio> 
#include<algorithm>
using namespace std; 
#define REP(i,n) for(int i=0;i<(n);++i) 
#define FOR(i,l,h) for(int i=(l);i<=(h);++i) 
#define FORD(i,h,l) for(int i=(h);i>=(l);--i) 
   
#define N 1010 
   
bool vis[N],g[N][N]; 
int low[N],dfn[N],subnets[N]; 
int n,tmpdfn,son; 
void init_tarjan()
{
    memset(vis,0,sizeof(vis)); 
    memset(subnets,0,sizeof(subnets)); 
    memset(g,0,sizeof(g));
    tmpdfn=0;
    son=0;   
    n=0; 
}
void tarjan(int u)
{
	vis[u]=1;
	dfn[u]=low[u]=++tmpdfn;
	for(int i=1;i<=n;++i)
	{
		if(g[u][i])
		{
			if(!vis[i])
			{
				if(u==1)
					++son;//root
				tarjan(i);
				low[u]=min(low[u],low[i]);
				if(u!=1&&low[i]>=dfn[u])
					++subnets[u];
			}
			else
			low[u]=min(low[u],dfn[i]);
		}
	}
}
/*void dfs(int u) 
{ 
    //FOR(v,1,n)
    for(int v=1;v<=n;++v)  
    if(g[u][v]) 
    { 
        if(!vis[v]) 
        { 
	    if(u==1)
		    ++son;
	    vis[v]=1; 
            low[v]=dfn[v]=++tmpdfn; 
            dfs(v); 
            low[u]=min(low[u],low[v]); 
            if(low[v]>=dfn[u]) 
            { 
                if(u!=1)    subnets[u]++; 
                //else    son++; 
            } 
        } 
        else    low[u]=min(low[u],dfn[v]); 
    } 
} */
void init(void) 
{ 
    low[1]=dfn[1]=1; 
    tmpdfn=1; 
    n=son=0; 
    memset(vis,0,sizeof(vis)); 
    vis[1]=1; 
    memset(subnets,0,sizeof(subnets)); 
    memset(g,0,sizeof(g)); 
} 
int main(void) 
{ 
    int u,v; 
    int Case=1;
    freopen("e:\\zoj\\zoj_1119.txt","r",stdin); 
    while(scanf("%d",&u)==1 && u) 
    { 
        scanf("%d",&v); 
        init_tarjan(); 
        if(u>n)  n=u; 
        if(v>n)  n=v; 
        g[u][v]=g[v][u]=1; 
        while(scanf("%d",&u)==1 && u) 
        { 
            scanf("%d",&v); 
            if(u>n)  n=u; 
            if(v>n)  n=v; 
            g[u][v]=g[v][u]=1; 
        } 
        //dfs(1);
	tarjan(1); 
        if(Case>1)   puts(""); 
        printf("Network #%d\n",Case++); 
        if(son>1)    subnets[1]=son-1; 
        bool find=0; 
        FOR(i,1,n)  if(subnets[i]) 
        { 
            if(!find)   find=1; 
            printf("  SPF node %d leaves %d subnets\n",i,subnets[i]+1); 
        } 
        if(!find)   puts("  No SPF nodes"); 
    } 
    return 0; 
}