2021.07.17 题解 CF1385E Directing Edges（拓扑排序）

2021.07.17 题解 CF1385E Directing Edges（拓扑排序）

CF1385E Directing Edges - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：

给定一个由有向边与无向边组成的图，现在需要你把所有的无向边变成有向边，使得形成的图中没有环。

如果可以做到请输出该图，否则直接输出"NO"。

注意多组询问。

分析：

对于一个有向无环图，一条边，拓扑序小的一端指向拓扑序大的一端，因此确定无向边的方向。

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<queue>

using namespace std;

const int N=2e5+10;

int n,m,t,xh[N],cnt,head[N],ru[N];

struct node{

	int to,next;

}a[N];

struct nodei{

	int from,to;

}ai[N];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

void add(int u,int v){

	++cnt;

	a[cnt].to=v;

	a[cnt].next=head[u];

	head[u]=cnt;

}

int topo(){

	queue<int>q;

	int ind=0;

	for(int i=1;i<=n;i++)if(!ru[i])q.push(i);

	while(!q.empty()){

		int x=q.front();

		q.pop();

		xh[x]=++ind;

		for(int i=head[x];i;i=a[i].next){

			int v=a[i].to;

			--ru[v];

			if(!ru[v])q.push(v);

		}

	}

	if(ind==n)return 1;//如果序号不等于n，有向边中一定有环啊，pass！

	else return 0;

}

int main(){

	t=read();

	while(t--){

		memset(head,0,sizeof(head));

		//memset(&a,0,sizeof(a));

		memset(xh,0x3f,sizeof(xh));

		memset(ru,0,sizeof(ru));

		cnt=0;

		int tot=0;

		n=read();m=read();

		for(int i=1;i<=m;i++){

			int op,u,v;

			op=read();u=read();v=read();

			if(!op){

				++tot;

				ai[tot].from=u;

				ai[tot].to=v;

			}else{

				add(u,v);

				++ru[v];

			}

		}

		if(topo()){

			cout<<"YES"<<endl;

			for(int i=1;i<=n;i++)for(int j=head[i];j;j=a[j].next)

			cout<<i<<" "<<a[j].to<<endl;

			//for(int i=1;i<=cnt;i++)cout<<a[i].from<<" "<<a[i].to<<endl;

			for(int i=1;i<=tot;i++){

				if(xh[ai[i].from]>xh[ai[i].to])cout<<ai[i].to<<" "<<ai[i].from<<endl;

				else cout<<ai[i].from<<" "<<ai[i].to<<endl;

			}

		}else cout<<"NO"<<endl;

	}

	return 0;

}

2021.07.17 题解 CF1385E Directing Edges（拓扑排序）的相关教程结束。