http://acm.pku.edu.cn/JudgeOnline/problem?id=1094拓?fù)渑判颍艽_定順序的情況是在拓?fù)渑判驎r每個時刻入度為0的頂點(diǎn)只有一個。
#include<iostream>
#include<fstream>
using namespace std;
int n,degree[30],res[30];
struct Node
{
int pos;
Node *next;
}node[30];
void insert(char a,char b)
{
int aa=a-'A';
int bb=b-'A';
Node *p=new Node;
p->pos=bb;
p->next=node[aa].next;
node[aa].next=p;
}
int top_sort()
{
bool flag=false;
int in[30]={0};
int i,tmp,top,sta[100];
for(i=0,top=0;i<n;i++)
{
in[i]=degree[i];
if(in[i]==0) sta[top++]=i;
}
if(top>1) flag=true;
/**//* for(i=0;i<n;i++)
printf("%d ",in[i]);
puts("");*/
for(i=0;i<n;i++)
{
if(top==0) return -1;
if(top>1) flag=true;
tmp=sta[--top];
res[i]=tmp;
Node *p=node[tmp].next;
while(p)
{
if(--in[p->pos]==0)
sta[top++]=p->pos;
p=p->next;
}
}
if(flag) return 0;
return 1;
}
int main()
{
bool flag,incon;
int i,m,num=0,tmp;
char str[4];
ifstream input;
input.open("in.txt");
// while(input>>n>>m)
while(scanf("%d%d",&n,&m))
{
if(n==0&&m==0) break;
flag=incon=false;
memset(degree,0,sizeof(degree));
for(i=0;i<n;i++)
node[i].next=NULL;
for(i=1;i<=m;i++)
{
scanf("%s",str);
// input>>str;
if((!flag)&&(!incon))
{
degree[str[2]-'A']++;
insert(str[0],str[2]);
tmp=top_sort();
if(tmp==-1)
{
num=i;
incon=true;
}
else if(tmp==1)
{
num=i;
flag=true;
}
}
}
if(flag)
{
printf("Sorted sequence determined after %d relations: ",num);
for(i=0;i<n;i++)
printf("%c",'A'+res[i]);
puts(".");
}
else if(incon) printf("Inconsistency found after %d relations.\n",num);
else printf("Sorted sequence cannot be determined.\n");
}
system("pause");
return 0;
}