http://acm.pku.edu.cn/JudgeOnline/problem?id=1094
poj 1094 toplogical_sort
题意 给出如下的相互关系(0 0结束) 要你判断是否在某一次读入后，能够判断所给关系
是矛盾的，或者能找出唯一符合这样关系的组合，或是最终也无法确定他们的关系。
4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0
方法 拓扑排序
每次读入一对关后，做一次floyd, 计算传递闭包.
然后判环,其实很简单，就是看有没有点i的map[i][i]=1;
有就证明有环！如果有环就矛盾了。
如果无环再判断是否能确定关系，(注意每次都把出入度数组清零!)计算每个点的出度+入度是否=n-1；
如果所有点都有这个关系，那么唯一的关系就确定了，接下来拓扑排序就能找出这个关系.
Source Code
| Problem: 1094 |
|
User: lovecanon |
| Memory: 208K |
|
Time: 32MS |
| Language: C++ |
|
Result: Accepted |
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int n,m,top,map[27][27],indegree[27],outdegree[27],mem[27],s[27];
char str[27],buf[10];
int floyd(){
int i,j,k;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++){
if(map[i][k]&&map[k][j]) map[i][j]=1;
}
for(i=0;i<n;i++)
if(map[i][i]) return 0;
return 1;
}
int calc(){
int i,j;
memset(indegree,0,sizeof(indegree));
memset(outdegree,0,sizeof(outdegree));
for(i=0;i<n;i++)
for(j=0;j<n;j++){
if(map[i][j]) {indegree[j]++;outdegree[i]++;}
}
for(i=0;i<n;i++)
if(indegree[i]+outdegree[i]!=n-1) return 0;
return 1;
}
void toplogical_sort(){
int i,j=0;
top=0;
for(i=0;i<n&&top<=1;i++) if(!indegree[i]) mem[++top]=i;
memset(s,0,sizeof(s));
while(top){
int cnt=mem[top--];
s[cnt]=1;
str[j++]=cnt+'A';
for(i=0;i<n;i++){
if(!s[i] && map[cnt][i]) indegree[i]--;
if(i!=cnt && !s[i] && indegree[i]==0) mem[++top]=i;
}
}
str[j]='\0';
}
int main(){
while(scanf("%d%d",&n,&m),n&&m){
memset(map,0,sizeof(map));
int i,flag1=0,flag2=0;
for(i=1;i<=m;i++){
scanf("%s",buf);
map[buf[0]-'A'][buf[2]-'A']=1;
if(flag1 || flag2) continue;
else if(!floyd()) {flag1=i;continue;}
else if(calc()) {toplogical_sort();flag2=i;}
}
if(flag1) printf("Inconsistency found after %d relations.\n",flag1);
else if(flag2) printf("Sorted sequence determined after %d relations: %s.\n",flag2,str);
else printf("Sorted sequence cannot be determined.\n");
}
return 0;
}