题解 P2017 【[USACO09DEC]晕牛Dizzy Cows】

小年轻w · 2017-04-09 14:56:21 · 题解

这题可以用拓扑排序，我们可以这样加边，先按拓扑排序，把入度为0 的加入 队列，（这题无向边入度不加），遍历他的所有边，如果碰到一条他连出去的无向边 并且这条无向边还没有被标记过，那么直接标记一下，这样做就一定能保证无环，如果最终所有的点里面还有点没有入队过，说明这些点在环中，则说明没有可行的方案，直接输出 -1。

#include <stdio.h>
#include<iostream>
#include <algorithm>
using namespace std ;
const int maxn = 1000016,maxe = 3000000 ;
struct node{
    int to,pre,val,from;
}e[maxe];
int x,y,n,e1,e2,cnt,num,h,t ;
int into[maxn],q[maxn],head[maxn] ;
inline void addedge(int x,int y,int w) 
{
    e[++cnt].to = y;e[cnt].from=x;
    e[cnt].pre = head[x] ;
    e[cnt].val=w; 
    head[x] =cnt;
}
int main(){
    scanf("%d%d%d",&n,&e1,&e2) ;
    for(int i=1;i<=e1;i++) {
        scanf("%d%d",&x,&y) ;
        addedge(x,y,0);into[y]++;
    } 
    for(int i=1;i<=n;i++) 
        if(into[i]==0) q[++t]=i;
    if(cnt%2==0) cnt++;
    for(int i=1;i<=e2;i++){
        scanf("%d%d",&x,&y);
        addedge(x,y,1);
        addedge(y,x,1);
    }
    while(h<t) {
        int u=q[++h] ; 
        for(int i=head[u];i;i=e[i].pre) {
            if(e[i].val==0) {
                into[e[i].to]--; 
                if(into[e[i].to]==0) q[++t]=e[i].to;
            } 
         }
         for(int i=head[u];i;i=e[i].pre)
             if(e[i].val==1) e[i^1].val=2;
     }
    for(int i=1;i<=cnt;i++)
        if(e[i].val==1) printf("%d %d\n",e[i].from,e[i].to);
    return 0 ;
}