大家好，又见面了，我是全栈君，今天给大家准备了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;
}
版权声明：本文博主原创文章。博客，未经同意不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116980.html原文链接：https://javaforall.net
