ACM入门之【拓扑排序】
·
拓扑排序的应用:判断图中是否有环。
如果一个图有拓扑排序，说明该图一个没有环。
//基本思路就是先将入度为0的点入队，然后再依次扩展减入读。
//最后判断点数够n不够就可以了
int d[N],st[N],n;
vector<int>ans;
bool check()
{
queue<int>q;
for(int i=1;i<=n;i++) if(!d[i]) q.push(i),ans.push_back(i),st[i]=1;
while(q.size())
{
int u=q.front(); q.pop();
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(st[j]) continue;
if(--d[j]==0) q.push(j),ans.push_back(j),st[j]=1;
}
}
if(ans.size()==n) return true;
return false;
}
入门习题:
848. 有向图的拓扑序列
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)