[USACO09DEC] Dizzy Cows 拓扑序

先对有向边跑拓扑排序，记录下每个点拓扑序，为了使最后的图不存在环，加入的\(p2\)条无向边\(u,v\)必须满足\(u\)拓扑序小于\(v\)拓扑序，否则加入的无向边会破坏拓扑DAG结构，由此确定加入的无向边方向。

#include <cstdio>

#include <queue>

using namespace std;

#define MAXN 100010

int head[MAXN],nxt[MAXN*2],vv[MAXN*2],tot;

inline void add_edge(int u, int v){

    vv[++tot]=v;

    nxt[tot]=head[u];

    head[u]=tot;

}

int n,p1,p2;

int rdu[MAXN];

int idx[MAXN],cnt;

queue <int> q;

inline void topsort(){

    for(int i=1;i<=n;++i) if(rdu[i]==0) q.push(i);

    while(!q.empty()){

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

        idx[u]=++cnt;

        for(int i=head[u];i;i=nxt[i]){

            int v=vv[i];

            --rdu[v];

            if(rdu[v]==0) q.push(v);

        }

    }

}

int main(){

    scanf("%d %d %d", &n, &p1, &p2);

    while(p1--){

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

        add_edge(u, v);

        ++rdu[v];

    }

    topsort();

    while(p2--){

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

        if(idx[u]<idx[v]) printf("%d %d\n", u, v);

        else printf("%d %d\n", v, u);

    }

    return 0;

}