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?
Solution
缩点，满足题意的充要条件是存在一条完整的链，这个可以用“是否存在唯一拓扑序”解决。
Code
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e5+; int pre[maxn],low[maxn],clock;
int scc[maxn],s[maxn],c,cnt;
int head[maxn],e[maxn],nxt[maxn],k;
void adde(int u,int v){
e[++k]=v;nxt[k]=head[u];head[u]=k;
}
int _head[maxn],_e[maxn],_nxt[maxn],_k;
void _adde(int u,int v){
_e[++_k]=v;_nxt[_k]=_head[u];_head[u]=_k;
}
int n,m; int r[maxn],vis[maxn];
int topo(){
for(int i=;i<=cnt;i++){
int tot=,u;
for(int i=;i<=cnt;i++)//偷懒
if(!r[i]&&!vis[i]) tot++,u=i;
if(tot>) return ;
vis[u]=;
for(int i=_head[u];i;i=_nxt[i])
r[_e[i]]--;
}
return ;
} void dfs(int u){
pre[u]=low[u]=++clock;
s[++c]=u;
for(int i=head[u];i;i=nxt[i]){
int v=e[i];
if(!pre[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(!scc[v]){
low[u]=min(low[u],pre[v]);
}
}
if(low[u]==pre[u]){
cnt++;
while(c){
scc[s[c]]=cnt;
if(s[c--]==u) break;
}
}
} void clear(){
memset(head,,sizeof(head));
memset(_head,,sizeof(_head));
memset(pre,,sizeof(pre));
memset(low,,sizeof(low));
memset(vis,,sizeof(vis));
memset(r,,sizeof(r));
c=cnt=k=_k=;
} int main(){
int T;
scanf("%d",&T);
while(T--){
clear();
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
adde(u,v);
}
for(int i=;i<=n;i++)
if(!pre[i]) dfs(i); for(int i=;i<=n;i++)
for(int j=head[i];j;j=nxt[j]){
int u=scc[i],v=scc[e[j]];
if(u==v) continue;
else _adde(u,v),r[v]++;
} if(topo()) printf("Yes\n");
else printf("No\n");
}
return ;
}