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;
}