首页 > 代码库 > POJ 2762 Going from u to v or from v to u?
POJ 2762 Going from u to v or from v to u?
Going from u to v or from v to u?
Time Limit: 2000ms
Memory Limit: 65536KB
This problem will be judged on PKU. Original ID: 276264-bit integer IO format: %lld Java class name: Main
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
Source
POJ Monthly--2006.02.26
解题：强连通缩点+拓扑排序。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 using namespace std; 17 const int maxn = 1005; 18 struct arc{ 19 int to,next; 20 arc(int x = 0,int y = -1){ 21 to = x; 22 next = y; 23 } 24 }; 25 int dfn[maxn],low[maxn],belong[maxn],tot; 26 int head[maxn],head2[maxn],in[maxn],scc,cnt; 27 stack<int>stk; 28 bool instack[maxn]; 29 arc e[500000]; 30 void add(int *hd,int u,int v){ 31 e[tot] = arc(v,hd[u]); 32 hd[u] = tot++; 33 } 34 void tarjan(int u){ 35 dfn[u] = low[u] = ++cnt; 36 stk.push(u); 37 instack[u] = true; 38 for(int i = head[u]; ~i; i = e[i].next){ 39 if(!dfn[e[i].to]){ 40 tarjan(e[i].to); 41 if(low[e[i].to] < low[u]) low[u] = low[e[i].to]; 42 }else if(instack[e[i].to] && dfn[e[i].to] < low[u]) low[u] = dfn[e[i].to]; 43 } 44 if(dfn[u] == low[u]){ 45 scc++; 46 int v; 47 do{ 48 v = stk.top(); 49 stk.pop(); 50 instack[v] = false; 51 belong[v] = scc; 52 }while(v != u); 53 } 54 } 55 bool topsort(){ 56 queue<int>q; 57 for(int i = 1; i <= scc; i++){ 58 if(in[i]) continue; 59 q.push(i); 60 } 61 if(q.size() > 1) return false; 62 while(!q.empty()){ 63 int u = q.front(); 64 q.pop(); 65 for(int i = head2[u]; ~i; i = e[i].next) 66 if(--in[e[i].to] == 0) q.push(e[i].to); 67 if(q.size() > 1) return false; 68 } 69 return true; 70 } 71 int main() { 72 int t,u,v,n,m; 73 scanf("%d",&t); 74 while(t--){ 75 scanf("%d %d",&n,&m); 76 for(int i = 0; i < maxn; i++){ 77 dfn[i] = low[i] = 0; 78 instack[i] = false; 79 in[i] = belong[i] = 0; 80 head[i] = head2[i] = -1; 81 } 82 scc = cnt = tot = 0; 83 while(!stk.empty()) stk.pop(); 84 for(int i = 0; i < m; i++){ 85 scanf("%d %d",&u,&v); 86 add(head,u,v); 87 } 88 for(int i = 1; i <= n; i++) 89 if(!dfn[i]) tarjan(i); 90 if(scc == 1) {puts("Yes");continue;} 91 for(int i = 1; i <= n; i++){ 92 for(int j = head[i]; ~j; j = e[j].next){ 93 if(i == e[j].to || belong[i] == belong[e[j].to]) continue; 94 in[belong[e[j].to]]++; 95 add(head2,belong[i],belong[e[j].to]); 96 } 97 } 98 if(topsort()) puts("Yes"); 99 else puts("No");100 }101 return 0;102 }
POJ 2762 Going from u to v or from v to u?
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。