大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
题意:给定一系列关系(仅仅存在大写字母),推断是否存在矛盾,
或无法确定关系。或能够确定唯一的关系
分析:利用拓扑排序。可是须要边输入关系边排序
矛盾:推断是否存在环
确定关系:能找出唯一的拓扑排序
不能确定关系:不存在环,且全部关系处理后,关系仍无法确定
注:假设出现矛盾,则无需推断接下来的关系了
#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; }
版权声明:本文博主原创文章。博客,未经同意不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116980.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...