我希望你是我独家记忆

一段永远封存的记忆,随风而去
posts - 263, comments - 31, trackbacks - 0, articles - 3
   :: 首页 :: 新随笔 ::  :: 聚合  :: 管理
//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, 
0sizeof(edge) ) ;
    memset( indeg, 
0sizeof(indeg) ) ;

    
int child ;
    
forint i=1; i<=inn; i++ )
    {
        
while( scanf( "%d"&child ) != EOF && child ) {
            edge[i][child] 
= 1 ; indeg[child]++ ;
        }
    }
//构建图形
}

void f_indeg()
{
    
forint sn=1; sn<=inn; sn++ ) {
        
forint en=1; en<=inn; en++ ) {
            
if( edge[en][sn] ) indeg[sn]++ ;
        }
        edge[sn][sn] 
= 0 ;
    }
//构建indeg[]入度
}

int Topsort()
{
//用栈输出单一拓扑排序
    int stack[size] ; int top = -1 ;
    
forint i=1; i<=inn; i++ ) {
        
if0 == 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++ ; 

        
forint j=1; j<=inn; j++ )
        {
            
if( edge[curnode][j] ) 
            {
                indeg[j]
-- ;
                
if0 == 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()
{
    
forint 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 ;
}

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