很久沒(méi)有在blog上寫解題報(bào)告了。。。前一陣子都在看書，看算導(dǎo)，看中大的書。。。差點(diǎn)被認(rèn)為是沒(méi)有在做ACM了。。。怪我自己。
在中大的書上看到一段寫的不錯(cuò)的toplogical sort的代碼，用它來(lái)過(guò)了一直沒(méi)過(guò)的1094，后來(lái)看到kid的代碼，發(fā)現(xiàn)他寫麻煩了。其實(shí)判環(huán)不用那么麻煩，在拓?fù)渑判蚶锞涂梢耘协h(huán)了。值得注意的是，每次刪點(diǎn)時(shí)都要判斷是否存在兩個(gè)或兩個(gè)以上的入度為0的點(diǎn)，因?yàn)檫@樣是不能determin的。如果沒(méi)有這一步就會(huì)wa，比如如下數(shù)據(jù)：
4 5
A<B
C<D
B<D
A<C
B<D
若沒(méi)有那么做的話，會(huì)在輸出
Sorted sequence determined after 4 relations：ACBD.
但是實(shí)際上在第四步還沒(méi)有確定。
代碼比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)
評(píng)論(3) 編輯 收藏 引用 所屬分類:
Problem Solving