Going from u to v or from v to u?
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 15494 | Accepted: 4100 |
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.
Output
The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.
Sample Input
1
3 3
1 2
2 3
3 1
Sample Output
Yes
Source
POJ Monthly--2006.02.26,zgl & twb
题目意思：
给一n个点、m条边的有向图，问是否随意选两个点u和v，是否能从u到达v或者从v到达u。
思路：
如果弱连通分量有多个，那么肯定是不可到达的，所以用并查集处理一下。
如果弱连通分量有多个，那么肯定是不可到达的，所以用并查集处理一下。
强连通分量内部随意两个点是互相到达的，不互相到达的点在强连通分量之间，所以先用tarjan强连通分量缩点，若入度为0的个数>=2||出度为0的个数>=2那么也是不可到达的。
各种条件判断一下即可。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <stack>
using namespace std; #define N 1005 int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
int abs(int x,int y){return x<?-x:x;} int n, m;
bool in[N];
int suo[N];
int cnt;
vector<int>ve[N];
int dfn[N], low[N], Time;
stack<int>st;
int father[N]; int findroot(int u){
if(father[u]!=u) father[u]=findroot(father[u]);
return father[u];
} void tarjan(int u){
dfn[u]=low[u]=Time++;
st.push(u);in[u]=true;
int i, j, k;
for(i=;i<ve[u].size();i++){
int v=ve[u][i];
if(dfn[v]==-){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(in[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
while(){
int x=st.top();
suo[x]=cnt;
in[x]=false;
st.pop();
if(x==u||st.empty()) break;
}
cnt++;
}
} main()
{
int i, j, k, u, v;
int t;
cin>>t; while(t--){
scanf("%d %d",&n,&m);
for(i=;i<=n;i++) ve[i].clear();
for(i=;i<m;i++){
scanf("%d %d",&u,&v);
ve[u].push_back(v);
}
Time=cnt=;
memset(dfn,-,sizeof(dfn));
while(!st.empty()) st.pop();
memset(in,false,sizeof(in));
for(i=;i<=n;i++){
if(dfn[i]==-){
tarjan(i);
}
}
int inn[N], out[N];
memset(inn,,sizeof(inn));
memset(out,,sizeof(out));
for(i=;i<=n;i++) father[i]=i;
for(i=;i<=n;i++){
for(j=;j<ve[i].size();j++){
int u=suo[i], v=suo[ve[i][j]];
if(u!=v){
father[findroot(v)]=findroot(u);
inn[v]++;
out[u]++;
}
}
} int num=;
for(i=;i<cnt;i++){
if(father[i]==i) num++;
}
if(num>) {
printf("No\n");continue;
} int n1, n2;
n1=n2=;
for(i=;i<cnt;i++){
if(!inn[i]) n1++;
if(!out[i]) n2++;
}
if(n1>||n2>) printf("No\n");
else printf("Yes\n");
}
}