Current Contest
Past Contests
Scheduled Contests Welcome
WJMZBMR Log Out
Mail:0(0)

[Usaco2009 Dec]Dizzy 头晕的奶牛

Time Limit:10000MS  Memory Limit:65536K
Total Submit:10 Accepted:0
Case Time Limit:1000MS

Description

Input

* 第1行: 三个由空格隔开的正数: N, M1和M2

* 第2到1+M1行: 第i+1行表示第i条单向道路，包含两个由空格隔开的整数: A_i和B_i

* 第2+M1到第1+M1+M2行: 第i+M1+1行表示第i条单向道路，包含两个由空格隔开的整数
X_i和Y_i

Output

* 第1到M2行: 第i行应该包含两个由空格隔开的整数: 根据你给第i条双向道路定义的的方
向，可能是X_i, Y_i，也可能是Y_i, X_i。这些双向道路必须按照输入的顺序
输出。如果无解，在单独的一行内输出"-1"。

Sample Input

4 2 3
1 2
4 3
1 3
4 2
3 2

Sample Output

1 3
2 4
2 3

Source

Gold
囧。。有意思的题目。。我一开始想的是随便找个点dfs，然后按深度连边，明显错的囧。。然后想对每个点dfs一遍求出能通过有向边到达哪些点，那么这些点与这个点连的无向边肯定要正向，结果很明显TLE囧。。要是比赛的话只能按这个骗点分了。。
当我苦思无果头痛万分的时候。。我感觉似乎应该是找某种规则来连边的，什么规则才能没有圈呢？DAG。。拓扑排序！囧。。我们学校春游的时候我就在想这个，春游都没玩好囧。。
Code：

/*
ID: Tom Chen
LANG: C++
TASK: dizzy
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=100000;
vector<int> E[maxn];
int In[maxn]={0},ord[maxn],n,m1,m2;
int main()
{
freopen("dizzy.in","r",stdin);
freopen("dizzy.out","w",stdout);
cin>>n>>m1>>m2;int s,t,cnt=0;
rep(i,m1)scanf("%d %d",&s,&t),–s,–t,E[s].pb(t),In[t]++;
queue<int> Q;rep(i,n)if(!In[i]) Q.push(i);
while(Q.size())
{
int t=Q.front();Q.pop();ord[t]=cnt++;
for(vector<int>::iterator i=E[t].begin();i!=E[t].end();i++)
if(!–In[*i]) Q.push(*i);
}
rep(i,m2)
{
scanf("%d %d",&s,&t),–s,–t;
if(ord[s]>ord[t])swap(s,t);
printf("%d %dn",s+1,t+1);
}
}