社区讨论

关于拓扑排序的疑惑

学术版参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mi7rmp29
此快照首次捕获于
2025/11/21 02:29
4 个月前
此快照最后确认于
2025/11/21 02:29
4 个月前
查看原帖
这个程序是不是正确的呀QAQ,求拓扑序列的。
为什么不要一个bool数组标记是否删除这个点?
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

const int MAXN=10005;
int n,m,cnt;//cnt是为了存储ans数组的下标
bool a[MAXN][MAXN];//邻接矩阵建图用
int indeg[MAXN],ans[MAXN];
//indeg[i]是第i个点的入度;ans[]是答案队列
queue <int> q;//

void input(void)
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x][y]=1;
		indeg[y]++;//建图,同时统计入度
	}
} 

void topo_sort(void)
{
	for(int i=1;i<=n;i++)
	 if(indeg[i]==0)
	  q.push(i);//将所有入度为0的点入队
	while(!q.empty())//开始搜索
	{
		const int u=q.front();
		ans[++cnt]=u;//入度为0的点记得放到答案队列里
		q.pop();
		for(int i=1;i<=n;i++)
		 if(a[u][i])//删边的操作转化为入度减1
		 {
			indeg[i]--;
			if(indeg[i]==0)//如果这个点变成入度为0,入队列
			 q.push(i); 
		 }
	}
}

void output(void)
{
	sort(ans+1,ans+1+n);//升序输出
	for(int i=1;i<=n;i++)
	 cout<<ans[i]<<' ';
}

int main()
{
	input();
	topo_sort();
	output();
	return 0;
}

回复

7 条回复,欢迎继续交流。

正在加载回复...