拓扑排序模版求调【玄关】
  • 板块学术版
  • 楼主MorningStarCzy
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/3/24 21:15
  • 上次更新2024/3/25 10:32:54
查看原帖
拓扑排序模版求调【玄关】
466596
MorningStarCzy楼主2024/3/24 21:15
#include<bits/stdc++.h>
using namespace std;
int u,v,n,m,a[505],cnt=1,in[505],to[505][505]={0};
priority_queue<int>Q;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		to[u][v]=1;
		in[v]++;
	}
	for(int i=1;i<=n;i++)
		if(in[i]==0) Q.push(i);
	while(!Q.empty())
	{
		int tmp=Q.top();
		Q.pop();
		a[cnt]=tmp;
		cnt++;
		for(int i=1;i<=n;i++)
		{
			if(to[tmp][i])
			{
				to[tmp][i]=0;
				in[i]--;
				if(in[i]==0) Q.push(i);
			}
		}
	}
	for(int i=1;i<=n-1;i++) cout<<a[i]<<" ";
	cout<<a[n];
	return 0;
}

输入:

4 3//两个数n,m。其中n表示点的个数,m表示边数
1 2//接下来m行,每行两个数u、v,代表u有一条边指向v
2 3
4 3

答案输出//如果有多种答案,编号小的排在前面

1 2 4 3//最后没有空格

我的输出

4 1 2 3//最后没有空格

玄关求调

2024/3/24 21:15
加载中...