题解 p2017 [USACO09DEC]晕牛Dizzy Cows

佚名 6年前 (2019-04-26) 随笔 1585人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

以样例为例。具体看代码及其中的注释

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 using namespace std;
 5 /*
 6     晕牛：拓扑排序
 7     有向边不成环，通过拓扑排序可以知道哪个入度少
 8     当你强行把应该在前面的强行和排序在后面的链接这一起
 9     则就会形成环，此时由于无向图的双向性不好处理，
10     于是，就规定输入第一个数字为出度，第二个数字为入度 
11     先把不会形成环的点跑一个拓扑排序
12     然后在判断让某些点强行连接后会不会有环
13     会就改方向，不会就不用管 
14 */
15 const int MAXN=100001;
16 int tot,a,b,n,p1,p2,cnt;int top[MAXN];
17 //top是拓扑排序后每个数的编号 
18 int head[MAXN],ver[MAXN],nxt[MAXN],deg[MAXN];
19 void add(int x,int y){
20     ver[++tot]=y;nxt[tot]=head[x];
21     head[x]=tot;deg[y]++;
22 }
23 void topsort(){//拓扑排序 
24     queue<int> q;
25     for(register int i=1;i<=n;i++)
26         if(deg[i]==0) q.push(i),top[i]=++cnt;
27     while(q.size()){
28         int x=q.front();q.pop();
29         for(register int i=head[x];i;i=nxt[i]){
30             int y=ver[i];
31             //y是该到某个边的出度点了 
32             if(!(--deg[y])) q.push(y),top[y]=++cnt;
33             //如果它入度为零的话，就把它塞进栈里 
34         }
35     }
36 }
37 int main(){
38     scanf("%d%d%d",&n,&p1,&p2);
39     for(register int i=1;i<=p1;i++)
40         scanf("%d%d",&a,&b),add(a,b);
41     topsort();
42     for(register int i=1;i<=p2;i++){
43         scanf("%d%d",&a,&b);
44         if(top[a]>top[b]) printf("%d %d\n",b,a);
45         else printf("%d %d\n",a,b);
46     }
47     return 0;
48 }