?
題目大意
?
一個公園中有 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
?
?
?
