May the force be with you!
posts - 52,  comments - 33,  trackbacks - 0
    很久没有在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 阅读(1421) 评论(3)  编辑 收藏 引用 所属分类: Problem Solving

FeedBack:
# re: 再谈Toplogical sort(pku 1094)
2009-01-25 01:23 | 风之伤
配上注释后,相当清晰。谢谢大大~~  回复  更多评论
  
# re: 再谈Toplogical sort(pku 1094)
2010-03-06 11:04 | Cinderella
请问一下 中大的书是哪本书  回复  更多评论
  
# re: 再谈Toplogical sort(pku 1094)
2010-03-06 13:09 | R2
@Cinderella
中山大学郭嵩山老师的《国际大学生程序设计竞赛例题解》  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


你是第 free hit counter 位访客




<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(4)

随笔分类(54)

随笔档案(52)

文章档案(1)

ACM/ICPC

技术综合

最新随笔

搜索

  •  

积分与排名

  • 积分 - 61526
  • 排名 - 357

最新评论

阅读排行榜

评论排行榜