随笔 - 87  文章 - 279  trackbacks - 0
<2008年4月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214427
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

 

#include  < iostream >
using   namespace  std;

const   int  MAXN  =   100 ;

int  list[MAXN][MAXN]; // 邻接表 
int  next[MAXN];
int  vInDegree[MAXN];  // 定点入度 
int  tpV[MAXN];  // 拓扑序列
int  n;  //  定点数 

int  TopoSort()
{
    
// 不能求最大并行组 
    
// 使用静态链盏
     int  i, t;
    
int  cnt  =   0 ;
    
int  top  =   - 1
    
for  (i = 0 ; i < n; i ++ {
        
if  (vInDegree[i]  ==   0 // 进盏 
            vInDegree[i]  =  top;
            top 
=  i;
        }

    }

    
while  (top  >=   0 {
        t 
=  top;
        top 
=  vInDegree[top];  // 出盏 
        tpV[cnt ++ =  t;
        
for  (i = 0 ; i < next[t]; i ++ {
            vInDegree[list[t][i]]
-- ;
            
if  (vInDegree[list[t][i]]  ==   0 // 进盏 
                vInDegree[list[t][i]]  =  top;
                top 
=  list[t][i];
            }

        }

    }

    
return  cnt;
}


int  main()
{
    
int  i, j, b;
    freopen(
" test.txt " " r " , stdin);
    scanf(
" %d " & n);
    memset(vInDegree, 
0 sizeof (vInDegree));
    
for  (i = 0 ; i < n; i ++ {
        scanf(
" %d " & b);
        scanf(
" %d " & next[b]);
        
for  (j = 0 ; j < next[b]; j ++ {
            scanf(
" %d " & list[b][j]);
            vInDegree[list[b][j]]
++ ;
        }

    }

    
if  (TopoSort()  ==  n)  {
        
for  (i = 0 ; i < n; i ++
            printf(
" %d  " , tpV[i]);
        printf(
" \n " );
    }
  else   {
        printf(
" can't not be Sort!\n " );
    }

    
// system("pause");
     return   0 ;
}


 

posted on 2006-10-11 13:05 阅读(1391) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法

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