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, 計算傳遞閉包.
然后判環(huán),其實很簡單，就是看有沒有點i的map[i][i]=1;
有就證明有環(huán)！如果有環(huán)就矛盾了。
如果無環(huán)再判斷是否能確定關系，(注意每次都把出入度數組清零!)計算每個點的出度+入度是否=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;
}