POJ 1094(トポロジ順序)

テーマリンク:http://poj.org/problem?id=1094
複数のグループの関係を与えて、唯一のトポロジ順序を構成できるかどうかを判断する.
考え方:
3つの状況を判断する:
①リングがあるかどうか
②秩序があるかどうか(一意性)
③トポロジカルなソートができますか?
この問題はやはり比較的にもつれています.唯一かどうかを先に考慮して、トポロジー的な順序を形成するかどうかを判断して、秩序化を考慮しています.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

const int INF=0x3f3f3f3f;
const int maxn=105;
int T,n,m;
int map[maxn][maxn];
int degree[maxn];
char p[maxn];
char str[10];

int topo_Sort(int n){
	int k=0,flag=1;
	int tmp[maxn];
	for(int i=0;i<n;i++)
		tmp[i]=degree[i];
	while(k<n){
		int m=0,index;
		for(int i=0;i<n;i++){
			if(!tmp[i]){
				m++;
				index=i;
			}
		}
		if(!m) return 0;//  
		if(m>1) flag=-1;//  
		tmp[index]--;
		p[k++]=index+'A';
		for(int j=0;j<n;j++){
			if(map[index][j]){
				tmp[j]--;
			}
		}
	}
	return flag;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
#endif
	while(~scanf("%d%d",&n,&m)){
		if(!n&&!m) break;
		memset(map,0,sizeof(map));
		memset(degree,0,sizeof(degree));
		int flag=0;
		for(int i=0;i<m;i++){
			scanf("%s",str);
			if(flag) continue;
			int a=str[0]-'A';
			int b=str[2]-'A';
			map[a][b]=1;
			degree[b]++;
			int sign=topo_Sort(n);
			if(sign==0){
				printf("Inconsistency found after %d relations.
",i+1);
				flag=1;
			}
			if(sign==1){
				printf("Sorted sequence determined after %d relations: ",i+1);
				for(int i=0;i<n;i++){
					printf("%c",p[i]);
				}
				puts(".");
				flag=1;
			}
		}
		if(!flag){
			printf("Sorted sequence cannot be determined.
");
		}
	}
	return 0;
}