poj 3177【Redundant Paths】

将图变成双连通图，缩点，考虑该点与其他点相连的个数，如果只有一条边与其他点相连，则需要加一条边，因为这里面的点只能通过一条边到其他点，加一条边让它们能够通过另一条边到达其他点。

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <vector>
 4 using namespace std;
 5 
 6 const int maxN = 5000+10;
 7 int low[maxN];
 8 int DFN[maxN];
 9 int degree[maxN];
10 int cnt;
11 
12 vector<int> edge[maxN];
13 
14 void Tarjan(int x,int fa)
15 {
16     low[x] = DFN[x] = cnt ++;
17 
18     int len = edge[x].size();
19     for(int i = 0;i < len;i ++)
20     {
21         int u = edge[x][i];
22         if(u == fa) continue;
23         if(!DFN[u]) 
24         {
25             Tarjan(u,x);
26             if(low[x] > low[u]) low[x] = low[u];
27         }
28         else if(low[x] > DFN[u])
29         {
30             low[x] = DFN[u];
31         }
32     }
33 }
34 
35 void UseTarjan()
36 {
37     memset(DFN,0,sizeof(DFN));
38     cnt = 1;
39 
40     Tarjan(1,1);
41 }
42 
43 bool isok(int x,int value)
44 {
45     int len = edge[x].size();
46     for(int i = 0;i < len;i ++)
47         if(edge[x][i] == value)
48             return false;
49 
50     return true;
51 }
52 
53 int main()
54 {
55     int n,m;
56 
57     cin >> n >> m;
58     for(int i = 0;i < m;i ++)
59     {
60         int u,v;
61         cin >> u >> v;
62         if(isok(u,v))
63         {
64         edge[u].push_back(v);
65         edge[v].push_back(u);
66         }
67     }
68 
69     UseTarjan();
70     
71     memset(degree,0,sizeof(degree));
72     for(int i = 1;i <= n;i ++)
73     {
74         int len = edge[i].size();
75         for(int j = 0;j < len;j ++)
76         {
77             if(low[i] != low[edge[i][j]])
78             {
79                 degree[low[i]] ++;
80                 //degree[low[edge[i][j]]] ++;
81             }
82         }
83     }
84 
85     int ans = 0;
86     for(int i = 1;i < cnt;i ++)
87     {
88         if(degree[i] == 1) ans++;
89     }
90 
91     cout << (ans + 1) / 2 << endl;
92 
93     return 0;
94 }