poj1094----拓扑排序
// Creat By 郭仔 2015年3月29日9:12:52
//画图演示一遍就能很好的理解了
/*题意:输入n, m,n表示26个大写字母组成的字母表中前n个字母,m表示将输入m对字母的大小关系式,
(ch1 < ch2)问根据输入多少个关系式时能惟一确定这n个字母有可能出现的关系,共有3 种情况:
(1)如果出现ch1 < ch2同时又有ch1 > ch2则表示这n个字母是inconsistency。
(2)能确定有惟一这n个的字母的拓扑序。
*/
//(3)不能根据输入的m对关系确定这n个字母逻辑大小的关系。
#include<iostream>
#include<cstring>
#include<cstdio>
#define MAX 30
int M,N;
bool tu[MAX][MAX];
int count[MAX];//记录点的入度的值
char order[MAX];
int topsort()
{
int i,j,k;
memset(count,0,sizeof(count));
memset(order,‘\0‘,sizeof(order));//每次拓扑都要初始化,很重要的
for(i=1;i<=N;i++)//这里是N而不是M,因为只要N个字母确定好拓扑顺序后,之后就不用输入了
{
for(j=1;j<=N;j++)
if(tu[i][j]) count[j]++;
}
bool flag=true;
for(k=1;k<=N;k++)
{
i=0;
for(j=1;j<=N;j++)
{
if(count[j]==0)
{
if(i==0) i=j;
else flag=false;
}
}
if(i==0) return 0;
count[i]=-1;
order[k-1]=‘A‘+i-1;
for(j=1;j<=N;j++)
if(tu[i][j]) count[j]--;
}
if(flag) return 1;
else return 2;
}
int main()
{
int i,j,resute,a,b;
char s[10];
while(scanf("%d%d",&N,&M)!=EOF)
{
if(M==0&&N==0)
break;
memset(tu,false,sizeof(tu));
bool h=false;
for(i=1;i<=M;i++)
{
scanf("%s",s);
if(h) continue;,
a=s[0]-‘A‘+1; b=s[2]-‘A‘+1;
tu[a][b]=true;
resute=topsort();
if(resute==0)
{
printf("Inconsistency found after %d relations.\n",i);
h=true;//标记啦
}
else if(resute==1)
{
printf("Sorted sequence determined after %d relations: %s.\n",i,order);
h=true;
}
}
if(!h) printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。