SPF Tarjan算法求无向图割点（关节点）入门题
2024-09-05 11:49:57
题目抽象，给出一个连通图的一些边，求关节点。以及每个关节点分出的连通分量的个数
邻接矩阵只要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 }
最新文章
- IIS 配置Http重定向到Https
- http://jingyan.baidu.com/article/86112f13582848273797879b.html
- Visual Studio 2013 Update 2 and with Update 2
- Bridage
- Apache的配置
- IDA strings view 中文字符的显示
- 高仿快车100--实战RadioGroup和RadioButton应用
- Mechanism:Limited Direct Execution
- 【转】10条你不可不知的css规则
- python 作用域
- SD从零开始62-63，不完全日志，业务伙伴及业务伙伴确定
- 《WEB渗透一.信息收集》
- PageAdmin CMS网站制作教程实例：如何制作一个报名表？
- python2在安装pywin32后出现ImportError: DLL load failed 解决方法
- POJ 1384 Intervals （区间差分约束，根据不等式建图，然后跑spfa）
- oracle查看表中数据的大小
- 有关C#中的引用类型的内存问题
- centos6，python3，通过pip安装pycurl出现报错提示
- Print之modile, level
- 1高并发server：多路IO之select