不知道为什么把有向边改掉了 调不动了
查看原帖
不知道为什么把有向边改掉了 调不动了
816504
封禁用户楼主2024/8/15 17:19
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=2e5+5;
int now,all,n,m;
struct Nor
{
	int x,y;
}nor[M];int cot;
struct Edge
{
	int to,next;
}edge[M];int tot,head[N];
void add(int u,int v)
{
	edge[++tot]=(Edge){v,head[u]};
	head[u]=tot;
}
int num[N],ind[N];
bool into()
{
	while(all>0)
	{
		int cut=0;
		for(int i=1;i<=n;i++)
		{
			if(ind[i]==0)
			{
				cut=i;
				break;
			}
		}
		if(cut==0) return 0;
		num[cut]=++now;
		for(int i=head[cut];i;i=edge[i].next)
		{
			all--;
			ind[edge[i].to]--;
		}
	}
	return 1;
}
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d",&n,&m);
//		zero();
		tot=0;cot=0;now=0;all=0;
		for(int i=1;i<=n;i++) num[i]=0;
		for(int i=1;i<=n;i++) ind[i]=0;
		for(int i=1;i<=n;i++) head[i]=0;
		for(int i=1;i<=m;i++)
		{
			int ol,u,v;
			scanf("%d %d %d",&ol,&u,&v);
			nor[++cot]=(Nor){u,v};
			if(ol==1)
			{
				add(u,v);
				ind[v]++;
				all++;
			}
		}
		if(into()==0)
		{
			printf("NO\n");
			continue;
		}
		else
		{
			printf("YES\n");
		}
		for(int i=1;i<=n;i++)
		{
			if(num[i]==0) num[i]=++now;
		}
		for(int i=1;i<=cot;i++)
		{
			if(num[nor[i].x]<num[nor[i].y])
			{
				printf("%d %d\n",nor[i].x,nor[i].y);
			}
			else 
			{
				printf("%d %d\n",nor[i].y,nor[i].x);
			}
		}
	}
}
2024/8/15 17:19
加载中...