BZOJ1773: [Usaco2009 Dec]Dizzy 头晕的奶牛

题解:

这道题没有SPJ...

但是http://oj.jdfz.com.cn:8081/oldoj/problem.php?id=1013这里是可以正常提交的...

考虑一开始给出的若干有向边,若存在环一定是无解的.

否则,我们利用现在的DAG随意得到一个拓扑序列.

给剩下的边定向时,我们总是让在序列前面的点指向序列后面的点.

这样一定是满足要求的.

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
#define M 100010
int head[N],next[M],end[M],in[N];
inline void addedge(int a,int b){
    static int q=1;
    end[q]=b;
    next[q]=head[a];
    head[a]=q++;
    ++in[b];
}
 
int q[N],fr,ta,ins[N];
int main(){
    int n,m1,m2;
    cin>>n>>m1>>m2;
    int a,b,i,j;
    for(i=1;i<=m1;++i){
        scanf("%d%d",&a,&b);
        addedge(a,b);
    }
    for(i=1;i<=n;++i)
        if(!in[i])
            q[ta++]=i;
    while(fr!=ta){
        i=q[fr++];
        for(j=head[i];j;j=next[j])
            if(!--in[end[j]])
                q[ta++]=end[j];
    }
    if(ta!=n)
        cout<<-1<<endl;
    else{
        for(i=0;i<ta;++i)
            ins[q[i]]=i;
        for(i=1;i<=m2;++i){
            scanf("%d%d",&a,&b);
            if(ins[a]>ins[b])
                swap(a,b);
            printf("%d %d\n",a,b);
        }
    }
    return 0;
}