题解 CF1385E 【Directing Edges】

原题传送门

题面翻译得已经非常清晰了，唯一的缺点是没有给出输入输出解释。

不过观察样例可知，第一个数为数据组数，接下来每一个数据第一行输入 \text{n m} ，表示这是一个 \text{n} 个点， \text{m} 条边的图。结点编号从 1 开始。接下来 \text{m} 行，输入 \text{type,u,v} ，表示这条边连接了两个顶点 \text{u} 和 \text{v} ，如果 \text{type=1} ，则这条边是一条 \text{u} 到 \text{v} 的有向边，否则是一条无向边。

要求输出该图指的是按原来的有向边输入格式输出原有有向边和定向后的无向边。

具体大家一会儿可以看代码，此处不再赘述。

接下来讲解做法。

首先无解的情况必然是原图有向边成环的情况。

那么我们就在求解的过程中判断原图是否已经有环即可。

考虑有解的情况，原图中给出的有向边必然形成DAG。

想到拓扑排序。

在拓扑排序中，所有的有向边都是拓扑序小的点指向拓扑序大的点。

那么我们只要对原有的有向边进行拓扑排序，然后判断有没有环，最后有解的话，先输出所有有向边，然后让无向边中拓扑序小的指向大的再输出即可。

Code

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

const int N=2e5+10;

int t,n,m,top[N],fir[N],tot,q[N][2],cnt,du[N];
queue <int> que;
struct node {int to,nex;} e[N];

void add(int u,int v)
{
    e[++tot].to=v;
    du[v]++;
    e[tot].nex=fir[u];
    fir[u]=tot;
    return ;
}

bool top_sort()//核心
{
    int u,sum=0;
    for(int i=1;i<=n;i++) if(!du[i]) que.push(i);
    while(!que.empty())
    {
        u=que.front(); que.pop();
        top[u]=++sum;//注意这里的拓扑序
        for(int i=fir[u];i;i=e[i].nex)
        {
            du[e[i].to]--;
            if(!du[e[i].to]) que.push(e[i].to);
        }
    }
    if(sum != n) return false;
    return true;//如果可以拓扑每个点一定都入队了一次
}

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    scanf("%d",&t);
    int op,u,v;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        tot=cnt=0;//多组数据的初始化
        while(!que.empty()) que.pop();
        for(int i=1;i<=n;i++) {fir[i]=du[i]=0; top[i]=1e9;}//注意这里初始拓扑序为正无穷
        while(m--)
        {
            scanf("%d%d%d",&op,&u,&v);
            if(op) add(u,v);//对于边的种类分别处理
            else {q[++cnt][0]=u; q[cnt][1]=v;}
        }
        if(top_sort())
        {
            puts("YES");
            for(int i=1;i<=n;i++)
                for(int j=fir[i];j;j=e[j].nex)
                    printf("%d %d\n",i,e[j].to);
            for(int i=1;i<=cnt;i++)
                if(top[q[i][0]] > top[q[i][1]]) printf("%d %d\n",q[i][1],q[i][0]);//拓扑序小的指向拓扑序大的
                else printf("%d %d\n",q[i][0],q[i][1]);
        }
        else puts("NO");
    }
//  fclose(stdin); fclose(stdout);
    return 0;
}

感谢阅读！如果这篇题解能帮到您，就请您留下您的赞吧！您的点赞和评论是对作者最大的鼓励！