社区讨论
关于拓扑排序的疑惑
学术版参与者 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 条回复,欢迎继续交流。
正在加载回复...