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

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

阅读量：6941 次

发布时间：2019-06-27

本文共 4171 字，大约阅读时间需要 13 分钟。

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

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

// time 16ms

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
              10 #include 
              
                11 #include 
               
                 12 #include 
                
                  13 #include 
                 
                   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 
     
        3 #include 
      
         4 #include 
       
          5 #include 
        
           6 #include 
         
            7 #include 
          
            8 #include 
           
             9 #include 
            
              10 #include 
              11 #include 
              
                12 #include 
               
                 13 #include 
                
                  14 #include 
                 
                   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 }