首页 > 代码库 > POJ3352 Road Construction

POJ3352 Road Construction

Road Construction

来自这里。

双连通分量

题意:比较裸的题意,就是给一个无向图,问添加多少条边后能使整个图变成双连通分量

分析:建议先学了双连通分量的相关知识,因为这题是算是个模板题(我自己写了模板,过了这题,但是还没有充分测试),如果没学好相关知识即便这个模板题也不好懂

双连通分量分为【点双连通分量,边双连通分量】,这题是个边双连通分量,就是要求出整个图的边双连通分量,然后缩点,然后找出缩点后每个点的度,度为1的点其实是树叶,答案就是(leaf+1)/2去上整,为什么是这个答案,网上的解释是,每次找到两个叶子他们的最近公共祖先最远,然后给这两个叶子连一条边,然后依次找出这样的点,所以是(leaf+1)/2

现在为问题就是1.怎么缩点。2.怎么统计缩点后的度

 

 ////////////  注意一点  ///////////////////

这题的题意是保证了图是连通的,所以才有上面的计算公式,所以只要dfs一次,如果图不连通,可能要dfs多次,并且不是上面的计算公式(leaf+1)/2

 

两种做法:

1.简化tarjan,在边双连通分量中,每个点low[u]其实已经记录是这个点u是属于哪个边双连通分量了,low[u] = low[v] ,那么点u和点v在一个边双连通分量中,所以我们可以不用急着找什么连通分量,我们先运行一次dfs,把那个顶点的low都计算出来,然后我们查看原图的每一条边(u,v),看看原图的两个点u,v是不是属于不同的连通分量,是的话,缩点后它们之间就有一条边,那么就要统计它们的度。统计完后就可以知道哪些是叶子了

2.上面的做法,是在dfs后再处理边双连通分量的,可以一边dfs,一边就找到边双连通分量呢?是可以,这个方法才是要讲的重点

首先有几个知识点

先搞清楚,树边,后向边,前向边,横叉边是什么,维基百科有讲解

对原图缩点后,变成了一棵无根树,树的边是什么?其实就是原图的桥,所以,我们可以在dfs过程中把所有的桥保存下来,放在一个表中,然后dfs完后,直接去查看那个表,桥的两端是两个点,这两个点是一个属于两个不同的边双连通分量的,所以我们可以直接统计这些缩点的度

判断桥的条件比较简单,对于一条树边(注意是树边),在dfs过程中是从u到v的(可以看做u是v的父亲),且满足low[v] > dfn[u] , 那么无向边(u,v)就是桥,就可以把这条边保存在表中

另外在这个dfs中借助了栈(方法1可以用栈,也可以不用,因为方法1简化了tarjan),在dfs过程中访问了点就不断入栈。在找到一条桥后,就准备将一些点出栈,因为这些准备出栈的点都是属于一个边双连通分量的,出栈的终于条件是,点v最后出来,点u不能出,注意,点u不能,点u不是属于点v的那个连通分量的,因为桥(u,v)分开了他们

 

方法1:简化了tarjan的过程,注意vis的意思,其实它的作用代替了栈的作用,vis[i]=0,1,2分别表示还没访问,已经访问但是还没退出,访问完并退出,它表示的是一种时间上的顺序

这个代码跑得快,0ms

技术分享
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 #define N 1010
 6 #define M 1010
 7 #define INF 0x3f3f3f3f
 8 
 9 int n,tot;
10 int head[N];
11 struct edge
12 {
13     int u,v,next;
14 }e[2*M];
15 int dfn[N],low[N],vis[N],dcnt,bcnt,de[N];
16 
17 inline int min(int x , int y)
18 {
19     return x<y ? x:y;
20 }
21 
22 void add(int u ,int v ,int k)
23 {
24     e[k].u = u; e[k].v = v;
25     e[k].next = head[u]; head[u] = k++;
26     u = u^v; v = u^v; u = u^v;
27     e[k].u = u; e[k].v = v;
28     e[k].next = head[u]; head[u] = k++;
29 }
30 
31 void dfs(int u ,int fa)
32 {
33     dfn[u] = low[u] = ++dcnt;
34     vis[u] = 1;
35     for(int k=head[u]; k!=-1; k=e[k].next)
36     {
37         int v = e[k].v;
38         if(v == fa) continue;
39         if(!vis[v]) //树边
40         {
41             dfs(v,u);
42             low[u] = min(low[u] , low[v]);
43         }
44         else if(vis[v] == 1) //后向边
45             low[u] = min(low[u] , dfn[v]);
46         //如果是横叉边为vis[v] == 2 , 跳过
47     }
48     vis[u] = 2;
49 }
50 
51 void solve()
52 {
53     memset(dfn,0,sizeof(dfn));
54     memset(de,0,sizeof(de));
55     memset(vis,0,sizeof(vis));
56     dcnt = bcnt = 0;
57     for(int i=1; i<=n; i++)
58         if(!vis[i])
59             dfs(i,i);
60     for(int u=1; u<=n; u++)
61         for(int k=head[u]; k!=-1; k=e[k].next)
62         {
63             int v = e[k].v;
64             if(low[u] != low[v]) //属于不同的边连通分量
65                 de[low[u]]++;
66         }
67     int leaf = 0;
68     for(int i=1; i<=n; i++)
69         if(de[i] == 1)
70             leaf++;
71     cout << (leaf+1)/2 << endl;
72 }
73 
74 int main()
75 {
76     while(cin>> n >> tot)
77     {
78         int u,v,k = 0;
79         memset(head,-1,sizeof(head));
80         for(int i=0; i<tot; i++,k+=2)
81         {
82             cin >> u >> v;
83             add(u,v,k);
84         }
85         solve();
86     }
87     return 0;
88 }
View Code

 

方法2:这个代码慢啊,150ms,而且不知道模板还有没有其他的问题,至少是还没能处理重边

技术分享
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 #define N 1010
  6 #define M 1010
  7 #define min(a,b) ((a)<(b)?(a):(b))
  8 
  9 int n,tot;
 10 int head[N],dfn[N],low[N],belong[N],de[N],stack[N],bridge[M][2],ins[N],dcnt,bcnt,top,bnum;
 11 struct edge
 12 {
 13     int u,v,next;
 14 }e[2*M];
 15 
 16 void add(int u ,int v ,int k)
 17 {
 18     e[k].u = u; e[k].v = v; e[k].next = head[u]; head[u] = k++;
 19     u = u^v;  v = u^v;  u = u^v;
 20     e[k].u = u; e[k].v = v; e[k].next = head[u]; head[u] = k++;
 21 }
 22 
 23 void dfs(int u ,int fa)
 24 {
 25     dfn[u] = low[u] = ++dcnt;
 26     stack[++top] = u; ins[u] = 1;
 27     for(int k=head[u]; k!=-1; k=e[k].next)
 28     {
 29         int v = e[k].v;
 30         if(v == fa) continue;
 31         if(!dfn[v]) //树边
 32         {
 33             dfs(v,u);
 34             low[u] = min(low[u] , low[v]);
 35             if(low[v] > dfn[u]) //边(u,v)为桥,可以统计一个边连通分支
 36             {
 37                 //保存桥
 38                 bridge[bnum][0] = u;
 39                 bridge[bnum++][1] = v;
 40                 
 41                 ++bcnt;
 42                 while(true)
 43                 {
 44                     int x = stack[top--];
 45                     ins[x] = 0;
 46                     belong[x] = bcnt;
 47                     if(x == v) break;
 48                 }//注意点u并没有出栈,因为点u属于另一个边连通分量
 49             }
 50         }
 51         else if(ins[v]) //后向边
 52             low[u] = min(low[u] , dfn[v]);
 53         //横叉边为(dfn[v] && !ins[v]),跳过
 54     }
 55 }
 56 
 57 void solve()
 58 {
 59     memset(dfn,0,sizeof(dfn));
 60     memset(de,0,sizeof(de));
 61     memset(ins,0,sizeof(ins));
 62     dcnt = bcnt = top = bnum = 0;
 63     dfs(1,-1);
 64     if(top)
 65     {
 66         ++bcnt;
 67         while(true)
 68         {
 69             int x = stack[top--];
 70             ins[x] = 0;
 71             belong[x] = bcnt;
 72             if(x == 1) break;
 73         }
 74     }
 75 
 76     for(int i=0; i<bnum; i++) //取出所有的桥
 77     {
 78         int u = bridge[i][0];
 79         int v = bridge[i][1];
 80         de[belong[u]]++;
 81         de[belong[v]]++;
 82         //统计缩点后的的度
 83     }
 84     int leaf = 0;
 85     for(int i=1; i<=bcnt; i++)
 86         if(de[i] == 1)
 87             leaf++;
 88     cout << (leaf+1)/2 << endl;
 89     
 90 //可以把下面的注释去掉,看看记录的内容,帮组理解
 91 /*
 92     for(int u=1; u<=n; u++)
 93         cout << u << "[" << belong[u] << "]" << endl;
 94     for(int i=1; i<=bcnt; i++)
 95         cout << "[" << de[i] << "]" << endl;
 96     for(int i=0; i<bnum; i++)
 97     {
 98         int u = bridge[i][0], v = bridge[i][1];
 99         printf("桥: %d %d\n",u,v);
100         printf("缩点后的边: %d %d\n",belong[u] , belong[v]);
101     }
102 */
103 }
104 
105 int main()
106 {
107     while(cin >> n >> tot)
108     {
109         memset(head,-1,sizeof(head));
110         int u,v,k=0;
111         for(int i=0; i<tot; i++,k+=2)
112         {
113             cin >> u >> v;
114             add(u,v,k);
115         }
116         solve();
117     }
118     return 0;
119 }
View Code

 

POJ3352 Road Construction