poj 1094(拓扑排序,三种情况:1正好排好,2正好有环,3到最后也没排好,也没有环,多重解)
2021/8/12 23:10:46
本文主要是介绍poj 1094(拓扑排序,三种情况:1正好排好,2正好有环,3到最后也没排好,也没有环,多重解),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,flag,edge[30][30],indegree[30],indgr_tmp[30],ans[30]; void topo(){ int i,j,s,pos; for(i=0;i<n;i++){ indgr_tmp[i] = indegree[i]; } pos = 0; for(i=0;i<n;i++){ s = 0; for(j=0;j<n;j++){ if(indgr_tmp[j]==0){ s++; pos = j; } } if(s==0){ flag = 1;//环 return; } if(s>1){ flag = -1;//有多重解 } ans[i] = pos; indgr_tmp[pos]=-1; for(j=0;j<n;j++){ if(edge[pos][j]){ indgr_tmp[j]--; } } } } int main(){ int m,i,j,sign; char a[1000][3]; while(scanf("%d%d",&n,&m)==2&&n){ sign = 0; memset(indegree,0,sizeof indegree); memset(edge,0,sizeof edge); for(i=0;i<m;i++){ scanf("%s",a[i]); if(sign==1)continue; flag = 0; edge[a[i][0]-'A'][a[i][2]-'A'] = 1; indegree[a[i][2]-'A']++; memset(ans,0,sizeof ans); memset(indgr_tmp,0,sizeof indgr_tmp); topo(); if(flag==1){ printf("Inconsistency found after %d relations.\n",i+1); sign = 1; } if(flag==0){ printf("Sorted sequence determined after %d relations: ",i+1); for(j=0;j<n;j++){ printf("%c",ans[j]+'A'); } printf(".\n"); sign = 1; } } if(flag==-1){ printf("Sorted sequence cannot be determined.\n"); } } return 0; }
这篇关于poj 1094(拓扑排序,三种情况:1正好排好,2正好有环,3到最后也没排好,也没有环,多重解)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?