首页 > 代码库 > POJ 2762 tarjan缩点+拓扑
POJ 2762 tarjan缩点+拓扑
Going from u to v or from v to u?
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 14566 | Accepted: 3846 |
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
题目意思：
给出一个结点数目为n,边数为m的有向图，若随意选出两个结点x、y，若能从x到y或者(注意，不是而且)y到x，输出Yes，否则输出No。
思路：
在强连通里肯定成立，若不成立，肯定在两个强连通分量里面，那么狠容易想到缩点分块了。画了几个图后发现若分块后的图为单链那么肯定成立，若不是单链即有分叉的话那么不成立，自然而然想到拓扑了，每次删除一个入度为0的点，就看一下入度为0的点为多少个，若>1则不成立。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <vector> 6 #include <queue> 7 #include <stack> 8 using namespace std; 9 10 #define N 10005 11 12 int low[N], dfn[N], dfn_clock; 13 int instack[N], a[N], in[N]; 14 int n, m; 15 stack<int>st; 16 vector<int>ve[N],out[N]; 17 int ans, num; 18 19 void init(){ 20 int i; 21 for(i=0;i<=n;i++){ 22 ve[i].clear();instack[i]=1; 23 out[i].clear(); 24 } 25 memset(dfn,0,sizeof(dfn)); 26 memset(in,0,sizeof(in)); 27 } 28 29 void tarjan(int u){ 30 int v, i, j; 31 dfn[u]=low[u]=dfn_clock++; 32 st.push(u); 33 for(i=0;i<ve[u].size();i++){ 34 v=ve[u][i]; 35 if(!dfn[v]){ 36 tarjan(v); 37 low[u]=min(low[u],low[v]); 38 } 39 else if(instack[v]){ 40 low[u]=min(low[u],dfn[v]); 41 } 42 } 43 if(low[u]==dfn[u]){ 44 ans++; 45 while(1){ 46 v=st.top();st.pop(); 47 instack[v]=0; 48 a[v]=ans; 49 if(v==u){ 50 break; 51 } 52 } 53 } 54 } 55 56 main() 57 { 58 int i, j, k; 59 int x, y; 60 int t; 61 cin>>t; 62 63 while(t--){ 64 scanf("%d %d",&n,&m); 65 init(); 66 while(m--){ 67 scanf("%d %d",&x,&y); 68 ve[x].push_back(y); 69 } 70 dfn_clock=1;ans=0; 71 for(i=1;i<=n;i++){ 72 if(!dfn[i]) 73 tarjan(i); 74 } 75 for(i=1;i<=n;i++){ 76 for(j=0;j<ve[i].size();j++){ 77 x=ve[i][j]; 78 if(a[x]!=a[i]){ 79 in[a[x]]++; 80 out[a[i]].push_back(a[x]); 81 } 82 } 83 } 84 int aa, f; 85 // printf("%d\n",ans); 86 // for(i=1;i<=n;i++){ 87 // printf("%d ",a[i]); 88 // } 89 // cout<<endl; 90 for(i=1;i<=ans;i++){ 91 aa=0;f=0; 92 for(j=1;j<=ans;j++){ 93 if(!in[j]) aa++; 94 if(!in[j]&&!f){ 95 for(k=0;k<out[j].size();k++){ 96 in[out[j][k]]--; 97 } 98 in[j]=-1;f=1; 99 } 100 101 }102 103 if(aa>1) break;104 105 }106 if(aa<=1) printf("Yes\n");107 else printf("No\n");108 }109 }
POJ 2762 tarjan缩点+拓扑
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。