当前位置:网站首页>poj 1094 Sorting It All Out (拓扑排序)
poj 1094 Sorting It All Out (拓扑排序)
2022-07-06 15:10:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
题意:给定一系列关系(仅仅存在大写字母),推断是否存在矛盾,
或无法确定关系。或能够确定唯一的关系
分析:利用拓扑排序。可是须要边输入关系边排序
矛盾:推断是否存在环
确定关系:能找出唯一的拓扑排序
不能确定关系:不存在环,且全部关系处理后,关系仍无法确定
注:假设出现矛盾,则无需推断接下来的关系了
#include<stdio.h>
#include<string.h>
int n,m,vis[30],rd[30],flag[30],map[30][30],cnt;
char t[30];
int tpsort()
{
int i,j,k,num,mark=1;
cnt=0;
memset(vis,0,sizeof(vis)); //标记是否訪问
for(i=0;i<n;i++)
if(flag[i]){
num=0;
for(j=0;j<n;j++) //计算入度为0的个数
if(flag[j]&&!rd[j]&&!vis[j])
num++;
if(num==0) //若不存在入度为0结点,则存在环
return 0;
if(num>1) //若入度为0的结点大于1。说明无法确立唯一的拓扑关系
mark=0;
for(j=0;j<n;j++){
if(flag[j]&&!rd[j]&&!vis[j]){
t[cnt++]=j+'A';
vis[j]=1;
break;
}
}
for(k=0;k<n;k++)
if(map[j][k])
rd[k]--;
}
if(!mark)
cnt=0;
return 1;
}
int main()
{
int i,j,mark,pos,r[30];
char s[5];
while(scanf("%d%d",&n,&m)!=EOF){
if(m==0&&n==0)
break;
mark=1;
memset(map,0,sizeof(map));
memset(flag,0,sizeof(flag)); //标记该元素是否存在
memset(r,0,sizeof(r));
for(i=1;i<=m;i++){
scanf("%s",s);
if(mark==1){
flag[s[0]-'A']=flag[s[2]-'A']=1;
if(s[1]=='>'){
map[s[2]-'A'][s[0]-'A']=1; //记录边的关系
r[s[0]-'A']++; //记录入度
}
else{
map[s[0]-'A'][s[2]-'A']=1;
r[s[2]-'A']++;
}
for(j=0;j<n;j++)
rd[j]=r[j]; //辅助空间。防止过程中拓扑排序将入度改变了
mark=tpsort();
if(!mark)
pos=i;
if(mark&&cnt==n){ //当没有出现环且关系都确定
mark=2;
pos=i;
t[cnt]=0; //字符数组最后附空字符
}
}
}
if(mark==0)
printf("Inconsistency found after %d relations.\n",pos);
else if(mark==1)
printf("Sorted sequence cannot be determined.\n");
else if(mark==2)
printf("Sorted sequence determined after %d relations: %s.\n",pos,t);
}
return 0;
}
版权声明:本文博主原创文章。博客,未经同意不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116980.html原文链接:https://javaforall.cn
边栏推荐
- Mysql database basic operations DML
- 12、 Start process
- return 关键字
- NPDP certification | how do product managers communicate across functions / teams?
- 十二、启动流程
- Unity3d minigame unity webgl transform plug-in converts wechat games to use dlopen, you need to use embedded 's problem
- (18) LCD1602 experiment
- 每日一题:力扣:225:用队列实现栈
- 图像的spatial domain 和 frequency domain 图像压缩
- Management background --3, modify classification
猜你喜欢
UE4蓝图学习篇(四)--流程控制ForLoop和WhileLoop
The SQL response is slow. What are your troubleshooting ideas?
Attack and defense world miscall
RESNET rs: Google takes the lead in tuning RESNET, and its performance comprehensively surpasses efficientnet series | 2021 arXiv
将MySQL的表数据纯净方式导出
CocosCreator+TypeScripts自己写一个对象池
机试刷题1
[leetcode daily clock in] 1020 Number of enclaves
Memorabilia of domestic database in June 2022 - ink Sky Wheel
0 basic learning C language - digital tube
随机推荐
Solve project cross domain problems
Dealing with the crash of QT quick project in offscreen mode
anaconda安装第三方包
[sdx62] wcn685x will bdwlan Bin and bdwlan Txt mutual conversion operation method
uniapp设置背景图效果demo(整理)
Gd32f4xx serial port receive interrupt and idle interrupt configuration
Seata aggregates at, TCC, Saga and XA transaction modes to create a one-stop distributed transaction solution
Inno Setup 打包及签名指南
C# 三种方式实现Socket数据接收
AI enterprise multi cloud storage architecture practice | Shenzhen potential technology sharing
RESNET rs: Google takes the lead in tuning RESNET, and its performance comprehensively surpasses efficientnet series | 2021 arXiv
3DMAX assign face map
Leetcode question brushing (XI) -- sequential questions brushing 51 to 55
2022-07-05 use TPCC to conduct sub query test on stonedb
qt quick项目offscreen模式下崩溃的问题处理
Management background --2 Classification list
pytorch_YOLOX剪枝【附代码】
自定义 swap 函数
Attack and defense world ditf Misc
如何实现文字动画效果