【Usaco2009 gold】头晕的奶牛
Description
奶牛们发现，在农场里面赛跑是很有趣的一件事。可是她们一旦在农场里面不断地转圈，就会变得头晕目眩。众所周知，眩晕的奶牛是无法产奶的。于是，农夫约翰想要把他农场里面的双向道路全部改为单向道路，使得他的农场里面一个“圈”都没有，以避免他的奶牛们被搞得晕头转向。如果奶牛可以经过若干条道路回到起点，那么这些道路就称为一个“圈”。
农场有N（1 <= N <= 100000）片草地，编号为1到N。这些草地由M1（1 <= M1 <= 100000）条单向道路和M2（1 <= M2 <= 100000）条双向道路连接起来。任何一条道路都不会把一片草地和这篇草地本身连接起来。但是，任意两片草地之间都可能有多条道路连接。不保证任意两片草地之间都有路径相连。
你的任务是给所有的双向道路设定一个方向，使得整个农场（只剩下单向道路）最后一个圈都没有。也就是说，不存在一个单向道路序列的终点和起点重合。数据保证一开始就有的单向道路中，一个圈都没有。而且一开始就有的单向道路不能改变。
单向道路的起点是草地A_i（1 <= A_i <= N），终点是草地B_i（1 <= B_i <= N）。双向道路连接草地X_i（1 <= X_i <= N）和Y_i（1 <= Y_i <= N）。
考虑下面这个样例：
草地1和3，2和3，2和4之间的道路是双向的。还有单向道路连接草地1和2，4和3。一种给双向道路定义方向的方法是，让三条双向道路的方向分别是1到3，2到3，3到4：
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
反思&题解
比赛思路： 乱建了一个图瞎搞了差不多2h，最后放弃
正解思路： 看到有向无环图，很显然想到拓扑排序（别问我为什么，其他大佬说的），将固定的有向边连好之后选入度为零的点一次做拓扑排序，之后对于x和y两个点选取拓扑序小的点作为起点就行了（玄学~~）
反思： 对于各种算法的理解还是要更深一点
CODE
#include<bits/stdc++.h>
using namespace std;
struct arr
{
int next,to;
}edge[500005];
int cnt,n,m1,rudu[100005],head[100005],m2,num[100005],tot;
queue<int>q;
void add(int u,int v)
{
edge[++cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;
}
int main()
{
freopen("dizzy.in","r",stdin);freopen("dizzy.out","w",stdout); scanf("%d%d%d",&n,&m1,&m2);int i;for (i=1;i<=m1;i++){
int x,y;scanf("%d%d",&x,&y);rudu[y]++;add(x,y);}tot=0;for (i=1;i<=n;i++)if (!rudu[i]) q.push(i);while (!q.empty()){
int u=q.front();q.pop();num[u]=++tot;for (i=head[u];i;i=edge[i].next){
int v=edge[i].to;if (!(--rudu[v])) q.push(v);} }for (i=1;i<=m2;i++){
int x,y;scanf("%d%d",&x,&y);if (num[x]<num[y]) printf("%d %d\n",x,y);else printf("%d %d\n",y,x);}return 0;
}