【题意】：
有N个房间，M条有向边，问能否毫无顾虑的随机选两个点x, y，使从①x到达y，或者，②从y到达x，一定至少有一条成立。注意是或者，不是且。
【思路】：
先考虑，x->y或者y->x是什么意思，如果是且的话就简单了，就直接判断整个图是不是强联通图即可，但是这道题是或，那么可以随手画出一个DAG
poj2106。比如1->3, 2->3 这样很明显是不行的，1,2没有联通，那么如果是这样1->2->3 就可以了，或者是1->2->3->1，这样也是可以的。
很显然，整个图中某一时刻入度同时为0的点的数量num≤1即可以找出合理方案，反之当某一时刻num>1时则不能。
考虑到图不可能是3个点这么简单，可以先求出强联通分量，因为分量中的每个点都可以相互到达，然后将每个联通分量缩点，这样就不用分别考虑。然后
对于每个缩点的入度判断可以使用topo排序判断。到此完毕。
topogun3合并拓扑层。
#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判断某一时刻有无多个点的入度同时为0queue<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; }
