poj 3352【Road Construction】

狂晕，是我做题太少了吧？我竟然直接按输入输出的模式做题，即输出“Output for Sample Input 1”，呜呜，WA了几次就是因为这个。。。。。。。。。。。。。。。。。。。。。。。。。。。

View Code

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