很久沒有在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 閱讀(1450)
評論(3) 編輯 收藏 引用 所屬分類:
Problem Solving