HDU 3394 Railway(点双连通分量)

 

题目大意

 

一个公园中有 n 个景点,景点之间通过无向的道路来连接,如果至少两个环公用一条路,路上的游客就会发生冲突;如果一条路不属于任何的环,这条路就没必要修

问,有多少路不必修,有多少路会发生冲突

 

做法分析

 

首先,这题不是边双连通的。要求的是点双连通分量。我们知道,每个点双连通分量又叫做块。冲突边只可能出现在块中,判断的依据就是快中的边和点的数量关系。

如果边数大于点数,这个块中所有的边全部是冲突边

而那些不需要修建的路,明显是桥。这在 tarjan 求点双连通分量的时候,可以顺便的一起求出来

 

参考代码

HDU 3394
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <stack>
 6 
 7 using namespace std;
 8 
 9 const int N=10006;
10 struct Edge
11 {
12     int st, en;
13     Edge() {}
14     Edge(int a, int b)
15     {
16         st=a, en=b;
17     }
18 };
19 stack <Edge> palm;
20 vector <int> arc[N];
21 vector <Edge> block[N];
22 int dfn[N], low[N];
23 bool vs[N];
24 int n, m, ind, T, sum1, sum2;
25 
26 void tarjan(int u, int pre)
27 {
28     dfn[u]=low[u]=T++;
29     int len=(int)arc[u].size();
30     for(int i=0; i<len; i++)
31     {
32         int v=arc[u][i];
33         if(dfn[v]==-1)
34         {
35             palm.push(Edge(u, v));
36             tarjan(v, u);
37             if(low[u]>low[v]) low[u]=low[v];
38             if(dfn[u]<=low[v])
39             {
40                 for(Edge temp; !palm.empty(); )
41                 {
42                     temp=palm.top();
43                     if(dfn[temp.st]<dfn[v]) break;
44                     block[ind].push_back(temp), palm.pop();
45                 }
46                 block[ind++].push_back(Edge(u, v));
47                 palm.pop();
48                 if(dfn[u]<low[v]) sum1++;
49             }
50         }
51         else if(v!=pre && dfn[v]<dfn[u])
52         {
53             palm.push(Edge(u, v));
54             if(low[u]>dfn[v]) low[u]=dfn[v];
55         }
56     }
57 }
58 
59 int main()
60 {
61     while(scanf("%d%d", &n, &m), n!=0 || m!=0)
62     {
63         for(int i=0; i<n; i++) arc[i].clear();
64         for(int i=0, a, b; i<m; i++)
65         {
66             scanf("%d%d", &a, &b);
67             arc[a].push_back(b);
68             arc[b].push_back(a);
69         }
70         for(int i=0; i<n; i++) dfn[i]=-1, block[i].clear();
71         while(!palm.empty()) palm.pop();
72         ind=T=sum1=sum2=0;
73         for(int i=0; i<n; i++) if(dfn[i]==-1) tarjan(i, -1);
74         for(int i=0; i<ind; i++)
75         {
76             for(int j=0; j<n; j++) vs[j]=0;
77             int len=(int)block[i].size(), tot=0;
78             for(int j=0; j<len; j++)
79             {
80                 if(!vs[block[i][j].st]) vs[block[i][j].st]=1, tot++;
81                 if(!vs[block[i][j].en]) vs[block[i][j].en]=1, tot++;
82             }
83             if(len>tot) sum2+=len;
84         }
85         printf("%d %d\n", sum1, sum2);
86     }
87     return 0;
88 }

AC通道

HDU 3394 Railway

原文地址:https://www.cnblogs.com/zhj5chengfeng/p/2974550.html