首页 > 代码库 > [poj2762] Going from u to v or from v to u?(Kosaraju缩点+拓排)
[poj2762] Going from u to v or from v to u?(Kosaraju缩点+拓排)
转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud
Going from u to v or from v to u?
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 14778 | Accepted: 3911 |
Description
In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn‘t know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?
Input
The first line contains a single integer T, the number of test cases. And followed T cases.
The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly.
The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly.
Output
The output should contain T lines. Write ‘Yes‘ if the cave has the property stated above, or ‘No‘ otherwise.
Sample Input
13 31 22 33 1
Sample Output
Yes
题意：给一个图，问是否为单向连通。
Kosaraju+缩点，然后拓扑序搞一下，若只有一条没有分支的链，则Yes,否则No
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <vector> 5 using namespace std; 6 const int maxn=1010; 7 vector<int>G[maxn]; 8 vector<int>rG[maxn]; 9 vector<int>vs; 10 int vis[maxn]; 11 int cmp[maxn]; 12 int last[maxn]; 13 int deg[maxn]; 14 int next[maxn]; 15 int V; 16 vector<int>vc[maxn]; 17 void add_edge(int u,int v) 18 { 19 G[u].push_back(v); 20 rG[v].push_back(u); 21 } 22 void init(int n) 23 { 24 for(int i=0;i<n;i++) 25 { 26 G[i].clear(); 27 rG[i].clear(); 28 vc[i].clear(); 29 vis[i]=0; 30 last[i]=-1; 31 deg[i]=0; 32 next[i]=-1; 33 } 34 } 35 void dfs(int v) 36 { 37 vis[v]=1; 38 for(int i=0;i<G[v].size();i++) 39 { 40 if(!vis[G[v][i]])dfs(G[v][i]); 41 } 42 vs.push_back(v); 43 } 44 void rdfs(int v,int k) 45 { 46 vis[v]=1; 47 cmp[v]=k; 48 vc[k].push_back(v); 49 for(int i=0;i<rG[v].size();i++) 50 { 51 if(!vis[rG[v][i]])rdfs(rG[v][i],k); 52 } 53 } 54 int scc() 55 { 56 memset(vis,0,sizeof(vis)); 57 vs.clear(); 58 for(int i=0;i<V;i++) 59 { 60 if(!vis[i])dfs(i); 61 } 62 memset(vis,0,sizeof(vis)); 63 int k=0; 64 for(int i=vs.size()-1;i>=0;i--) 65 { 66 if(!vis[vs[i]])rdfs(vs[i],k++); 67 } 68 return k; 69 } 70 int main() 71 { 72 ios::sync_with_stdio(false); 73 int t; 74 cin>>t; 75 while(t--) 76 { 77 int n,m; 78 cin>>n>>m; 79 V=n; 80 init(n); 81 int u,v; 82 for(int i=0;i<m;i++) 83 { 84 cin>>u>>v; 85 add_edge(--u,--v); 86 } 87 int k=scc(); 88 memset(vis,0,sizeof(vis)); 89 int flag=1; 90 int num=0; 91 for(int i=0;i<k;i++) 92 { 93 for(int j=0;j<vc[i].size();j++) 94 { 95 u=vc[i][j]; 96 for(int l=0;l<G[u].size();l++) 97 { 98 v=G[u][l]; 99 if(cmp[u]!=cmp[v])100 {101 if(last[cmp[v]]==-1)102 {103 last[cmp[v]]=cmp[u];104 }105 else if(last[cmp[v]]==cmp[u])continue;106 else flag=0;107 if(next[cmp[u]]==-1)108 {109 next[cmp[u]]=cmp[v];110 }111 else if(next[cmp[u]]==cmp[v])112 {113 continue;114 }115 else flag=0;116 }117 }118 }119 }120 for(int i=0;i<k;i++)121 {122 if(last[i]==-1)num++;123 }124 if(flag&&num==1)cout<<"Yes"<<endl;125 else cout<<"No"<<endl;126 }127 128 return 0;129 }
[poj2762] Going from u to v or from v to u?(Kosaraju缩点+拓排)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。