题目抽象，给出一个连通图的一些边，求关节点。以及每个关节点分出的连通分量的个数
邻接矩阵只要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(" "); 95 printf("Network #%d ",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 ",i,subnets[i]+1); 106 } 107 } 108 if(!find) 109 printf(" No SPF nodes "); 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(" "); 109 printf("Network #%d ",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 ",i,subnets[i]+1); 120 } 121 } 122 if(!find) 123 printf(" No SPF nodes "); 124 } 125 return 0; 126 }