很久没有在blog上写解题报告了。。。前一阵子都在看书，看算导，看中大的书。。。差点被认为是没有在做ACM了。。。怪我自己。
在中大的书上看到一段写的不错的toplogical sort的代码，用它来过了一直没过的1094，后来看到kid的代码，发现他写麻烦了。其实判环不用那么麻烦，在拓扑排序里就可以判环了。值得注意的是，每次删点时都要判断是否存在两个或两个以上的入度为0的点，因为这样是不能determin的。如果没有这一步就会wa，比如如下数据：
4 5
A<B
C<D
B<D
A<C
B<D
若没有那么做的话，会在输出
Sorted sequence determined after 4 relations：ACBD.
但是实际上在第四步还没有确定。
代码比kid的短，呵呵。
——Simbaforrest
代码如下：
#include<iostream>
#include<cstring>
using namespace std;
int v,e;
int deg[26];
int sortAns[26],anstop;
bool adj[26][26];
int TopSort()
{
int ret=1;
bool sure=true;
//init
memset(deg,0,sizeof(deg));
//count degree
for(int i=0; i<v; i++)
{
for(int j=0; j<v; j++)
{
if(adj[i][j]==true)
++deg[j];
}
}
//make stack of 0 degree vertex
int top=-1;
int cnt=0;
for(int i=0; i<v; i++)
{
if(deg[i]==0)
{
++cnt;
deg[i]=top;
top=i;
}
}
if(cnt==0)
{
sure=true;
return ret=-1;//cycle exist
}
if(cnt>1)
{
sure=false;
ret=0;//unsure
}//go on to see if cycle exist
//sort
anstop=-1;
for(int i=0; i<v; i++)
{
if(top==-1)
{
//cycle exist
sure=true;
return ret = -1;
}
else
{
//find j as the 0 degree vertex
int j = top;
top = deg[top];
sortAns[++anstop]=j;//record the ans
//delete the vertex j
cnt=0;
for(int ni=0; ni<v; ni++)
{
if(adj[j][ni]==true)
{
--deg[ni];
//a new 0 degree vertex
if(deg[ni]==0)
{
++cnt;
deg[ni]=top;
top = ni;
}
}
}
if(cnt>1)
{
sure=false;
ret=0;//unsure
}//go on to see if cycle exist
}
}
if(sure==false)
return ret=0;
return ret;
}
int main()
{
while(cin>>v>>e,!(v==0&&e==0))
{
//init
memset(adj,0,sizeof(adj));
bool sure=false;
//read and solve
for(int i=0; i<e; i++)
{
char left,op,right;
cin>>left>>op>>right;
adj[left-'A'][right-'A']=1;
if(sure)
continue;
int ret=TopSort();
if(ret!=0)
{
sure=true;
if(ret==1)
{
cout<<"Sorted sequence determined after "<<i+1<<" relations: ";
for(int j=0; j<=anstop; j++)
cout<<(char)(sortAns[j]+'A');
cout<<"."<<endl;
}
else if(ret==-1)
{
cout<<"Inconsistency found after "<<i+1<<" relations."<<endl;
}
}
}
if(sure==false)
{
cout<<"Sorted sequence cannot be determined."<<endl;
}
}
return 0;
}
posted on 2008-05-15 12:13
R2 阅读(1438)
评论(3) 编辑 收藏 引用 所属分类:
Problem Solving