SPF Tarjan算法求无向图割点（关节点）入门题

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

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　SPF

题目抽象，给出一个连通图的一些边，求关节点。以及每个关节点分出的连通分量的个数

邻接矩阵只要16ms,而邻接表却要32ms, 花费了大量的时间在加边上。

// time 16ms

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <string>
  7 #include <vector>
  8 #include <set>
  9 #include <map>
 10 #include <stack>
 11 #include <queue>
 12 #include <sstream>
 13 #include <iomanip>
 14 using namespace std;
 15 typedef long long LL;
 16 const int INF = 0x4fffffff;
 17 const double EXP = 1e-5;
 18 const int MS = 1005;
 19 const int SIZE = 100005;
 20 
 21 int edges[MS][MS];
 22 int vis[MS];
 23 int dfn[MS];
 24 int low[MS];
 25 int subnets[MS];
 26 int nodes;
 27 int tdfn;
 28 int sons;
 29 
 30 void init()
 31 {
 32       low[1]=dfn[1]=1;
 33       tdfn=1;sons=0;nodes=0;
 34       memset(vis,0,sizeof(vis));
 35       vis[1]=1;
 36       memset(subnets,0,sizeof(subnets));
 37       memset(edges,0,sizeof(edges));
 38 }
 39 
 40 void DFS(int u)
 41 {
 42       for(int v=1;v<=nodes;v++)
 43       {
 44             if(edges[u][v])
 45             {
 46                   if(!vis[v])
 47                   {
 48                         vis[v]=1;
 49                         dfn[v]=low[v]=++tdfn;       //  初始化
 50                         DFS(v);                                //   low[v]的值已经求出
 51                         low[u]=min(low[u],low[v]);
 52                         if(low[v]>=dfn[u])
 53                         {
 54                               if(u!=1)
 55                                     subnets[u]++;
 56                               else
 57                                     sons++;
 58                         }
 59                   }
 60                   else                   //  v已经访问过了，v是u的祖先节点，（v，u）是一条回边
 61                         low[u]=min(low[u],dfn[v]);
 62             }
 63       }
 64 }
 65 
 66 int main()
 67 {
 68       int u,v,find,number=1;
 69       while(1)
 70       {
 71             scanf("%d",&u);
 72             if(!u)
 73                   break;
 74             init();
 75             scanf("%d",&v);
 76             if(u>nodes)
 77                   nodes=u;
 78             if(v>nodes)
 79                   nodes=v;
 80             edges[u][v]=edges[v][u]=1;
 81             while(1)
 82             {
 83                   scanf("%d",&u);
 84                   if(!u)
 85                         break;
 86                   scanf("%d",&v);
 87                   if(u>nodes)
 88                         nodes=u;
 89                   if(v>nodes)
 90                         nodes=v;
 91                   edges[u][v]=edges[v][u]=1;
 92             }
 93             if(number>1)
 94                   printf("\n");
 95             printf("Network #%d\n",number++);
 96             DFS(1);
 97             if(sons>1)
 98                   subnets[1]=sons-1;
 99             find=0;
100             for(int i=1;i<=nodes;i++)
101             {
102                   if(subnets[i])
103                   {
104                         find=1;
105                         printf("  SPF node %d leaves %d subnets\n",i,subnets[i]+1);
106                   }
107             }
108             if(!find)
109                   printf("  No SPF nodes\n");
110 
111       }
112       return 0;
113 }

邻接表 time==32ms

  1 // time 32ms
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <cmath>
  6 #include <algorithm>
  7 #include <string>
  8 #include <vector>
  9 #include <set>
 10 #include <map>
 11 #include <stack>
 12 #include <queue>
 13 #include <sstream>
 14 #include <iomanip>
 15 using namespace std;
 16 typedef long long LL;
 17 const int INF = 0x4fffffff;
 18 const double EXP = 1e-5;
 19 const int MS = 1005;
 20 const int SIZE = 100005;
 21 
 22 //int edges[MS][MS];
 23 struct edge
 24 {
 25       int v,next;
 26 }edges[(MS*MS)];      //  理论上是（MS*MS）<<1,超内存。但这种情况是超级极端。（MS*MS）足够
 27 int head[MS];
 28 
 29 int vis[MS];
 30 int dfn[MS];
 31 int low[MS];
 32 int subnets[MS];
 33 int nodes;
 34 int tdfn;
 35 int sons;
 36 int cnt;
 37 
 38 void init()
 39 {
 40       low[1]=dfn[1]=1;
 41       tdfn=1;sons=0;
 42       nodes=0;cnt=0;
 43       memset(vis,0,sizeof(vis));
 44       vis[1]=1;
 45       memset(subnets,0,sizeof(subnets));
 46       memset(edges,0,sizeof(edges));
 47       memset(head,-1,sizeof(head));
 48 }
 49 
 50 void add(int u,int v)
 51 {
 52       edges[cnt].v=v;edges[cnt].next=head[u];head[u]=cnt++;
 53       edges[cnt].v=u;edges[cnt].next=head[v];head[v]=cnt++;
 54 }
 55 
 56 void DFS(int u)
 57 {
 58       for(int i=head[u];i!=-1;i=edges[i].next)
 59       {
 60             int v=edges[i].v;
 61             if(!vis[v])
 62             {
 63                   vis[v]=1;
 64                   dfn[v]=low[v]=++tdfn;
 65                   DFS(v);
 66                   low[u]=min(low[u],low[v]);
 67                   if(low[v]>=dfn[u])
 68                   {
 69                         if(u!=1)
 70                               subnets[u]++;
 71                         else
 72                               sons++;
 73                   }
 74             }
 75             else
 76                   low[u]=min(low[u],dfn[v]);
 77       }
 78 }
 79 
 80 int main()
 81 {
 82       int u,v,find,number=1;
 83       while(1)
 84       {
 85             scanf("%d",&u);
 86             if(!u)
 87                   break;
 88             init();
 89             scanf("%d",&v);
 90             if(u>nodes)
 91                   nodes=u;
 92             if(v>nodes)
 93                   nodes=v;
 94            add(u,v);
 95             while(1)
 96             {
 97                   scanf("%d",&u);
 98                   if(!u)
 99                         break;
100                   scanf("%d",&v);
101                   if(u>nodes)
102                         nodes=u;
103                   if(v>nodes)
104                         nodes=v;
105                 add(u,v);
106             }
107             if(number>1)
108                   printf("\n");
109             printf("Network #%d\n",number++);
110             DFS(1);
111             if(sons>1)
112                   subnets[1]=sons-1;
113             find=0;
114             for(int i=1;i<=nodes;i++)
115             {
116                   if(subnets[i])
117                   {
118                         find=1;
119                         printf("  SPF node %d leaves %d subnets\n",i,subnets[i]+1);
120                   }
121             }
122             if(!find)
123                   printf("  No SPF nodes\n");
124       }
125       return 0;
126 }