狂暈，是我做題太少了吧？我竟然直接按輸入輸出的模式做題，即輸出“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 }

轉載于:https://www.cnblogs.com/Shirlies/archive/2012/09/14/2685517.html

總結

以上是生活随笔為你收集整理的poj 3352【Road Construction】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。