POJ 2762Going from u to v or from v to u?(强联通 + 缩点 + 拓扑排序)

【题意】：

有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 =  + ;

const int maxm =  + ;

int n, m, t;

struct edge{

    int to, next;

} ed[maxm<<];

int head[maxn<<], tot, cnt;

int dfn[maxn], low[maxn], num, stak[maxn], c[maxn];

int indu[maxn<<];

bool instack[maxn], vis[maxn];

inline void init(){

    memset( head ,-, sizeof(head) );

    memset( dfn, , sizeof(dfn) );

    memset( low, , sizeof(low) );

    memset( indu, , sizeof(indu) );

    memset( vis, , sizeof(vis) );

    tot = ;

    stak[] = cnt = num = ;

}

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] = ;

    stak[++stak[]] = x;

    for( int i=head[x]; i!=-; 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[]];

            c[p] = cnt+n;

            instack[p] = ;

        } while(stak[stak[]--]!=x );

    }

}

inline void scc( int x ){                   //缩点

    if( vis[x] ) return;

    vis[x] = ;

    for( int i=head[x]; i!=-; 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=; i<=cnt; i++ )

        if( !indu[i+n] ) q.push(i+n);

    if( q.size()> ) return ;

    while( !q.empty() ){

        int x = q.front(); q.pop();

        for( int i=head[x]; i!=-; i=ed[i].next ){

            int y =ed[i].to;

            indu[y]--;

            if(!indu[y]) q.push(y);

            if( q.size()> ) return ;

        }

    }

    return ;

}

int main(){

    // freopen("in.txt", "r", stdin);

    scanf("%d", &t);

    while( t-- ){

        init();

        scanf("%d%d", &n, &m);

        for( int i=; i<m; i++ ){

            int u, v;

            scanf("%d%d", &u, &v);

            add( u, v );

        }

        for( int i=; i<=n; i++ )

            if( !dfn[i] ) tarjan(i);

        for( int i=; i<=n; i++ ) scc(i);

        if( topo() ) puts("Yes");

        else puts("No");

    }

    return ;

}