Posted on 2008-08-18 19:47
Hero 阅读(425)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
//WZR 1022 C++ Accepted 0.001 233 KB
//家谱树－－拓扑排序
//能加大括号的要加大括号－－在if中没有大括号，WA了好多
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int size = 150 ;
int edge[size][size] ;
int indeg[size] ;
int out[size] ;
int ct_out ;
bool OK ;
int inn ;
void input()
{
memset( edge, 0, sizeof(edge) ) ;
memset( indeg, 0, sizeof(indeg) ) ;
int child ;
for( int i=1; i<=inn; i++ )
{
while( scanf( "%d", &child ) != EOF && child ) {
edge[i][child] = 1 ; indeg[child]++ ;
}
}//构建图形
}
void f_indeg()
{
for( int sn=1; sn<=inn; sn++ ) {
for( int en=1; en<=inn; en++ ) {
if( edge[en][sn] ) indeg[sn]++ ;
}
edge[sn][sn] = 0 ;
}//构建indeg[]入度
}
int Topsort()
{//用栈输出单一拓扑排序
int stack[size] ; int top = -1 ;
for( int i=1; i<=inn; i++ ) {
if( 0 == indeg[i] ) stack[++top] = i ;
}//建立入度为0的栈stack[]
int cnt_node = 0 ; ct_out = -1 ;
while( top >= 0 )
{
//printf( "%d\n", stack[top] ) ;
int curnode = stack[top--] ; //indeg[curnode] = -1 ;//容易忘记
out[++ct_out] = curnode ; cnt_node++ ;
for( int j=1; j<=inn; j++ )
{
if( edge[curnode][j] )
{
indeg[j]-- ;
if( 0 == indeg[j] ) stack[++top] = j ;
}//不要忘了加大括号--WA了好多
}
}
if( cnt_node < inn ) { printf( "Topsort error--cycle!\n" ) ; return 0 ; }
return 1 ;
}
void process()
{
//f_indeg() ;
Topsort() ;
}
void output()
{
for( int i=0; i<ct_out; i++ )
printf( "%d ", out[i] ) ;
printf( "%d\n", out[ct_out] ) ;
}
int main()
{
while( scanf( "%d", &inn ) != EOF )
{
input() ;
process() ;
output() ;
}
return 0 ;
}