codeforces1385E Directing Edges

https://codeforces.com/contest/1385/problem/E

我这个经典构造竟然写错了，当年小号上黄的比赛的D题就是这个构造

给出一些边，要求指定边的方向让图没有有向环

那么直接按编号小的连向编号大的就行了

如果给出一些边有些有方向，有些无方向

那么直接拓扑排序，入度为0的入队，按队列出的顺序给点编号，还是从小编号连向大编号就行了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> p;
const int maxl=3e5+10;

int n,m,cas,k,cnt,tot,ans;
int du[maxl],ind[maxl];
char s[maxl];
bool in[maxl]; 
vector<int> e[maxl];
struct ed{int u,v;}edg[maxl];
queue<int> q;

inline void prework()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		e[i].clear(),du[i]=0;
	int x,u,v;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&u,&v);
		if(x==1)
			e[u].push_back(v),++du[v];
		edg[i]=ed{u,v};
	}
} 

inline void mainwork()
{
	for(int i=1;i<=n;i++)
	if(du[i]==0)
		q.push(i);
	ans=1;
	int u,v;cnt=0;
	while(!q.empty())
	{
		u=q.front();q.pop();
		ind[u]=++cnt;
		for(int v:e[u])
		{
			du[v]--;
			if(!du[v])
				q.push(v);
		}
	}
	if(cnt!=n)
		ans=0;
}

inline void print()
{
	if(!ans)
		puts("NO");
	else
	{
		puts("YES");int u,v;
		for(int i=1;i<=m;i++)
		{
			u=edg[i].u;v=edg[i].v;
			if(ind[u]>ind[v])
				swap(u,v);
			printf("%d %d\n",u,v);
		}
	}
}

int main()
{
	int t=1;
	scanf("%d",&t);
	for(cas=1;cas<=t;cas++)
	{
		prework();
		mainwork();
		print();
	}
	return 0;
}