晕牛-题解

查看原题请戳这里

每错，这是一道拓扑排序的题。

为什么这么说呢？

因为拓扑排序的前提要求是进行排序的图必须是DAG。我们在看这道题的要求，就会发现，当你把所有双向边改成单向边以后，这个图就一定是一个DAG，否则一定无解。

呢么，我们该怎么进行拓扑排序呢？

首先，对于给出的有向边，我们按照正常的拓扑排序的方式进行排序即可。 对于无向边，我们要双向连边，但是不更新入度。每当我们在拓扑排序是遍历到一条没有被处理过的双向边时，只需要把这条边的起点记录为当前正在遍历的节点即可。（想一想，为什么）· 附一下代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 0x7fffffff
#define ll long long

using namespace std;
struct Edge{
    int from,to,next,del;
}edge[2000005];
int t,a,b,n,p1,p2,head,tail,que[100001],d[100001],k[100001]; 
void add(int x,int y,int pd)
{
    edge[++t].to = y;
    edge[t].from = x;
    edge[t].next = d[x];
    d[x] = t;
    edge[t].del = pd;
}
int main()
{
    scanf(“%d%d%d”,&n,&p1,&p2);
    for( int i = 1; i <= p1; i++)
    {
        scanf(“%d%d”,&a,&b);
        add(a,b,0);
        k[b] ++;
    }
    if(t % 2 == 0) t++;
    for( int i = 1; i <= n; i++)
        if(k[i] == 0) que[++tail] = i;
    for( int i = 1; i <= p2; i++)
    {
        scanf(“%d%d”,&a,&b);
        add(a,b,1);
        add(b,a,1);
    }
    while(head < tail)
    {
        head++;
        int u = que[head];
        for( int i = d[u]; i; i = edge[i].next)
        {
            if(edge[i].del == 0)
            {
                k[edge[i].to] –;
                if(k[edge[i].to] == 0) que[++tail] = edge[i].to;
            }
            else
            if(edge[i].del == 1) edge[i^1].del = 2;
        }
    }
    for( int i = 1;i <= t; i++)
        if(edge[i].del == 1)
            printf(“%d %d\n”,edge[i].from,edge[i].to);
    return 0;
}