tarjan算法求关节点

浏览数：31 / 时间：2015年06月08日

求无向图的关节点

dfn[]来存点的深度数

在一张深度优先搜索树中，如果u和v是两个顶点，且生成树中u是v的祖先，则必有dfn[u]<dfn[v]，表明u先被访问。

回边:原图中除了dfs树中的边外，还有的边叫回边；如：1->2,1->3,2->3中,dfs时1->2->3,这里dfs树中的边为1->2,2->3，那么1->3就是回边；

（1）如果点u是dfs生成树的根，那么u至少有2个子女。理由:因为一删除u，它的子女所在的子树就断开了。

（2）如果点u不是dfs生成树的根，那么u的一个子女w，从w或w的子孙出发或回边到达u的祖先。如果能够到达，那么点u就不是关节点了。

因此，可以对每个店v设一个新的数组low[]，来保存通过v能够到达的最低深度数。

low[v]=min{

　　dfn[u]

　　min（low[w]|w为点v的子孙）

　　min（dfn[x]|x和v构成回边)

};

因此顶点u是关节点的充要条件为:u为根结点时，有2个或以上的子女。u不是根结点的时候，它的一个子女w，有low[w]>=dfn[u]。

技术分享

low[w]>=dfn[u]表示顶点u的子女w，能够到达的最低深度数大于等于顶点u的深度数。及w的子女没有不存在指向u祖先的边。这是删除顶点u,u的子树就从dfs树中脱离了。

如上图中点6是关节点，因为点6的子女结点low[w]>=dfn[u],及不存在能够指向u祖先的回边。删除点6后，子树断开。

而点7不是关节点，因为点7的子女结点点8，存在一条回边，满足low[8]<dfn[7]，

删除点7后，子树未断开。

poj1523

  1 #include<stdio.h>
  2 #include<string.h>
  3 int map[1003][1003];
  4 int vis[1003];//标记
  5 int dfn[1003];//来存他的dfs树中深度数
  6 int depth;//深度
  7 int subnets[1003]//删除该点后存其余能连通多少
  8 int nodenum;//点的个数
  9 int son;//根结点子女个数
 10 int low[1003];//存该点能够到达最低深度数
 11 void inin()
 12 {
 13     int i,j;
 14     memset(vis,0,sizeof(vis));
 15     memset(subnets,0,sizeof(subnets));
 16     depth=1;//开始时深度为1
 17     low[1]=dfn[1]=1;//根结点的深度为1
 18     son=0;
 19     vis[1]=1;
 20 }
 21 int min(int x,int y)
 22 {
 23     return x<y?x:y;
 24 }
 25 void dfs(int u)
 26 {
 27     int i,j;
 28     for(i=1;i<=nodenum;i++)
 29     {
 30         if(map[u][i])//如果两点连通
 31         {
 32             if(!vis[i])//如果之前为访问，即不是回边
 33             {
 34                 vis[i]=1;
 35                 depth++;//深度+1
 36                 dfn[i]=low[i]=depth;//更新
 37                 dfs(i);//继续搜索
 38                 low[u]=min(low[u],low[i]);//low[i]已在之前的dfs中更新,low[]存能够到达的最低深度数，所以要比较它本身和它的子女
 39                 if(low[i]>=dfn[u])//如果该结点为关节点
 40                 {
 41                     if(u==1)son++;//如果为根结点，son记录有几个子女
 42                     if(u!=1)subnets[u]++;//如果不是根结点，更新删除它后有多少的连通*分量*
 43                 }
 44             }
 45             else//如果之前已经被访问过，表明存在回路
 46             {
 47                 low[u]=min(low[u],dfn[i]);//更新low[]
 48             }
 49         }
 50     }
 51 }
 52 int main()
 53 {
 54     int i,j,u,v,flag,ff=1;
 55     while(1)
 56     {
 57         //输入部分
 58         nodenum=0;
 59         memset(map,0,sizeof(map));
 60         scanf("%d",&u);
 61         if(u==0)break;
 62         scanf("%d",&v);
 63         if(v>nodenum)nodenum=v;
 64         if(u>nodenum)nodenum=u;
 65         map[u][v]=map[v][u]=1;
 66         while(1)
 67         {
 68             scanf("%d",&u);
 69             if(u==0)break;
 70             scanf("%d",&v);
 71             if(v>nodenum)nodenum=v;
 72             if(u>nodenum)nodenum=u;
 73             map[u][v]=map[v][u]=1;
 74         }
 75         //初始化
 76         inin();
 77 
 78         dfs(1);//建树
 79         if(son>1)//如果根结点是关节点
 80         {
 81             subnets[1]=son-1;//更新subnets[1],即关节点的子女个数
 82         }
 83 
 84         if(ff>1)
 85             printf("\n");
 86         printf("Network #%d\n",ff++);
 87 
 88         flag=0;
 89         for(i=1;i<=nodenum;i++)
 90         {
 91             if(subnets[i])//如果连通分量存在，表示该点位关节点
 92             {
 93                 flag=1;
 94                 printf("  SPF node %d leaves %d subnets\n",i,subnets[i]+1);//subnets[]+1是因为还有分成两块，一个点；
 95             }
 96         }
 97         if(!flag)
 98             printf("  No SPF nodes\n");
 99     }
100 }