暑假集训Day7 D(拓扑排序判环)
2021/7/21 6:09:51
本文主要是介绍暑假集训Day7 D(拓扑排序判环),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接在这里:Problem - D - Codeforces
拓扑排序是个好东西,常用在途中各个点之间有先后顺序的问题的求解,同时在处理环问题中也有应用。在处理与环有关的问题时可以直接去掉与环无关的点,相当于在不断的简化这个图,不断通过入度为0的点删根节点,直到没有入度为0 的点,剩下的点全在环里面。删边的话直接将边所指向点的入度减一就行了。
以前遇到环的问题一般想的是tarjan,不过tarjan需要遍历边,而且删边的话只能对每一条边进行操作,需要枚举边,这里边数远远大于点数,所以用tarjan是不合适的。点的数量级小的话,用拓扑排序判断环是一个很好的选择。
1 #include "bits/stdc++.h" 2 using namespace std; 3 const int MAX=505; 4 int n,m; 5 int a[MAX][MAX]; 6 int in[MAX],ii[MAX]; 7 bool topu(){ 8 int i,j,zt,an=0; 9 queue <int> q; 10 while (!q.empty()) q.pop(); 11 for (i=1;i<=n;i++) 12 if (ii[i]==0) 13 q.push(i),an++; 14 while (!q.empty()){ 15 zt=q.front();q.pop(); 16 for (i=1;i<=n;i++) 17 if (a[zt][i] && ii[i]){ 18 ii[i]--; 19 if (ii[i]==0) q.push(i),an++; 20 } 21 } 22 return (an==n); 23 } 24 int main(){ 25 freopen ("d.in","r",stdin); 26 freopen ("d.out","w",stdout); 27 int i,j,u,v; 28 scanf("%d%d",&n,&m); 29 memset(a,0,sizeof(a)); 30 memset(in,0,sizeof(in)); 31 for (i=1;i<=m;i++){ 32 scanf("%d%d",&u,&v); 33 a[u][v]=1; 34 in[v]++; 35 } 36 for (i=1;i<=n;i++){ 37 for (j=1;j<=n;j++) ii[j]=in[j]; 38 ii[i]--; 39 if (topu()){ 40 printf("YES"); 41 return 0; 42 } 43 } 44 printf("NO"); 45 return 0; 46 }
这篇关于暑假集训Day7 D(拓扑排序判环)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?