题意:n个点,c1条有向边,c2条无向边,给定的c1条有向边不存在环,分配c2的方向使图不存在环
根据有向边统计入度,拓扑排序,碰到端点有入度为0的点的无相边,则方向为入度为0的边指向另一点
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+7;
int head[maxn], nxt[maxn], v[maxn], to[maxn], in[maxn], from[maxn];
int cnt,n,c1,c2;
void add(int x,int y, int z)
{to[++cnt] = y;from[cnt] = x;nxt[cnt] = head[x];v[cnt] = z;head[x] = cnt;
}
int main()
{while(cin>>n>>c1>>c2) {for(int i=0;i<c1;i++){int x,y;cin>>x>>y;add(x,y,0);in[y]++;}queue<int>q;for(int i=1;i<=n;i++)if(!in[i])q.push(i);if(cnt % 2 == 0)++cnt;for(int i=0;i<c2;i++){int x,y;cin>>x>>y;add(x,y,1);add(y,x,1);} while(!q.empty()) {int u = q.front();q.pop();for(int i=head[u];i;i=nxt[i]) {int vv = to[i];if(!v[i]){in[vv]--;if(!in[vv])q.push(vv);}else {if(v[i] == 1) {v[i^1] = 2;}}}}for(int i=1;i<=cnt;i++){if(v[i] == 1) {cout<<from[i]<<" "<<to[i] <<endl;}}}
}