【题意】：
有N个房间，M条有向边，问能否毫无顾虑的随机选两个点x, y，使从①x到达y，或者，②从y到达x，一定至少有一条成立。注意是或者，不是且。
【思路】：
先考虑，x->y或者y->x是什么意思，如果是且的话就简单了，就直接判断整个图是不是强联通图即可，但是这道题是或，那么可以随手画出一个DAG
比如1->3, 2->3 这样很明显是不行的，1,2没有联通，那么如果是这样1->2->3 就可以了，或者是1->2->3->1，这样也是可以的。
很显然，整个图中某一时刻入度同时为0的点的数量num≤1即可以找出合理方案，反之当某一时刻num>1时则不能。
考虑到图不可能是3个点这么简单，可以先求出强联通分量，因为分量中的每个点都可以相互到达，然后将每个联通分量缩点，这样就不用分别考虑。然后
对于每个缩点的入度判断可以使用topo排序判断。到此完毕。
#include <iostream> #include <cstring> #include <queue> #include <cstdio> using namespace std; const int maxn = 1000 + 5; const int maxm = 6000 + 5; int n, m, t; struct edge{ int to, next; } ed[maxm<<1]; int head[maxn<<1], tot, cnt; int dfn[maxn], low[maxn], num, stak[maxn], c[maxn]; int indu[maxn<<1]; bool instack[maxn], vis[maxn]; inline void init(){ memset( head ,-1, sizeof(head) ); memset( dfn, 0, sizeof(dfn) ); memset( low, 0, sizeof(low) ); memset( indu, 0, sizeof(indu) ); memset( vis, 0, sizeof(vis) ); tot = 1; stak[0] = cnt = num = 0; } inline void add( int u, int v ){ ed[++tot].to = v; ed[tot].next = head[u]; head[u] = tot; } inline int min( int a, int b ){ return a<b ? a:b; } inline void tarjan( int x ){ //求强联通 dfn[x] = low[x] = ++num; instack[x] = 1; stak[++stak[0]] = x; for( int i=head[x]; i!=-1; i=ed[i].next ){ int y = ed[i].to; if( !dfn[y] ){ tarjan(y); low[x] = min(low[x], low[y]); }else if(instack[y]) low[x] = min(low[x], dfn[y]); } if( low[x]==dfn[x] ){ ++cnt; do{ int p = stak[stak[0]]; c[p] = cnt+n; instack[p] = 0; } while(stak[stak[0]--]!=x ); } } inline void scc( int x ){ //缩点 if( vis[x] ) return; vis[x] = 1; for( int i=head[x]; i!=-1; i=ed[i].next ){ int y = ed[i].to; if( c[x]!=c[y] ){ add( c[x], c[y] ); indu[c[y]] ++; } scc(y); } } inline bool topo(){ //topo判断某一时刻有无多个点的入度同时为0 queue<int> q; for( int i=1; i<=cnt; i++ ) if( !indu[i+n] ) q.push(i+n); if( q.size()>1 ) return 0; while( !q.empty() ){ int x = q.front(); q.pop(); for( int i=head[x]; i!=-1; i=ed[i].next ){ int y =ed[i].to; indu[y]--; if(!indu[y]) q.push(y); if( q.size()>1 ) return 0; } } return 1; } int main(){ // freopen("in.txt", "r", stdin); scanf("%d", &t); while( t-- ){ init(); scanf("%d%d", &n, &m); for( int i=0; i<m; i++ ){ int u, v; scanf("%d%d", &u, &v); add( u, v ); } for( int i=1; i<=n; i++ ) if( !dfn[i] ) tarjan(i); for( int i=1; i<=n; i++ ) scc(i); if( topo() ) puts("Yes"); else puts("No"); } return 0; }