|
Language: Going from u to v or from v to u?
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 个房间，不同房间之间有单向通道，问是否任意两个房间 A 、B 都可以从 A 到 B 或从 B 到 A（有一条有就可以）。
在这题中，如果一些点是在同一个强连通分量中，那么这些点肯定能够相互到达，并且如果其他的点到达这里的任意一点，也就可以到达强连通分量中的所有点，所以首先需要对这题进行缩点。缩点之后图中就不存在环了，这时需要所有点间都至少有一条路，所以其实剩下了一条长链，并且是单向的，如果有双向的边就会被缩点，如果是数型图的话那么一个节点的多个子树就不能互相到达，所以一定是一条单向的长链，因此只要拓扑序判断就行。如果排序过程中，出现1个以上的点入度同时为0时，那么就不满足条件。
#include<iostream>
#include<queue>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;
co int N=1e3+1,M=6e3;
int n,m,dfn[N],low[N],num,c[N],deg[N],cnt;
int head[N],edge[M],next[M],tot;
int st[N],top;
bool ins[N];
int hc[N],ec[N],nc[N],tc;
il void add(int x,int y){
edge[++tot]=y,next[tot]=head[x],head[x]=tot;
}
il void add_c(int x,int y){
ec[++tc]=y,nc[tc]=hc[x],hc[x]=tc,++deg[y];
}
void tarjan(int x){
dfn[x]=low[x]=++num;
st[++top]=x,ins[x]=1;
for(int i=head[x];i;i=next[i]){
int y=edge[i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
++cnt;
int y;
do{
y=st[top--];
ins[y]=0;
c[y]=cnt;
}while(x!=y);
}
}
bool topsort(){
queue<int> q;
for(int i=1;i<=cnt;++i)
if(!deg[i]) q.push(i);
if(q.size()>1) return 0;
while(q.size()){
int x=q.front();q.pop();
for(int i=hc[x];i;i=nc[i]){
int y=ec[i];
if(!--deg[y]) q.push(y);
}
if(q.size()>1) return 0;
}
return 1;
}
void work(){
read(n),read(m);
tot=tc=1,num=cnt=top=0;
for(int i=1;i<=n;++i) head[i]=hc[i]=ins[i]=dfn[i]=low[i]=deg[i]=0;
for(int x,y;m--;){
read(x),read(y);
add(x,y);
}
for(int i=1;i<=n;++i)
if(!dfn[i]) tarjan(i);
for(int x=1;x<=n;++x)
for(int i=head[x];i;i=next[i]){
int y=edge[i];
if(c[x]!=c[y]) add_c(c[x],c[y]);
}
puts(topsort()?"Yes":"No");
}
int main(){
for(int t=read<int>();t--;) work();
return 0;
}POJ2762 Going from u to v or from v to u?
原文：https://www.cnblogs.com/autoint/p/11047966.html