拓扑排序哪错了(求解)
  • 板块学术版
  • 楼主阿哲朗读
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/1/22 20:50
  • 上次更新2023/10/28 11:31:11
查看原帖
拓扑排序哪错了(求解)
513326
阿哲朗读楼主2022/1/22 20:50
#include<bits/stdc++.h>
using namespace std;
int cnt,head[10001],rd[10001],p,n,m;
struct Edge
{
	int to,next;
}a[20001];
void AddEdge(int start,int end)
{
	cnt++;
	a[cnt].to=end;
	a[cnt].next=head[start];
	head[start]=cnt;
	return;
}
void Topsort()
{
	queue<int>q;
	for(int i=1;i<=n;i++)
	{
		if(rd[i]==0) q.push(i);
	}
	while(!q.empty())
	{
		int node=q.front();
		cout<<node<<" ";
		q.pop();
		p++;
		rd[node]=-1;
		for(int i=head[node];i;i=a[i].next)
		{
			rd[a[i].to]--;
			if(rd[a[i].to]==0) q.push(a[i].to);
		}
	}
	return;
}
int main()
{
	int x,y;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		AddEdge(y,x);
		rd[y]++;
	}
	Topsort();
	return 0;
 } 
2022/1/22 20:50
加载中...