poj1470解题报告

题意：最近公共祖先

题解：最近公共祖先

代码：

1，裸地在线算法

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;

const int MAXN = 1000 ;

int   N , M ;

int   father[MAXN] ;
int   count[MAXN]  ;
bool  vis[MAXN]    ;

int  main()
{
    int  i , j , a , b ;
    int  num , nr , suc ;
    char ch ;

    while ( scanf( "%d" , & N ) != EOF )
    {
        memset( vis   , 0 , sizeof( vis   ) ) ;
        memset( count , 0 , sizeof( count ) ) ;
        for( i = 0 ; i <= N ; i ++ ) father[i] = i ;

        for( i = 0 ; i < N ; i ++ )
        {
            scanf( "%d:(%d)" , & nr , & num ) ;
            while( num -- )
            {
                scanf( "%d" , & suc ) ;
                father[suc] = nr ;
            }
        }

        scanf( "%d" , & M ) ;
        while( M -- )
        {
            while( ch = getchar() )
            {
                if( ch == '(' )
                {
                     scanf( "%d%d" , & a , & b ) ;
                     getchar() ;
                     break ;
                }
            }
            while( father[a] != a )
            {
                vis[a] = 1 ;
                a = father[a] ;
            }
            vis[a] = 1 ;

            while( ! vis[b] )
                b = father[b] ;

            count[b] ++ ;
            memset( vis , 0 , sizeof( vis ) ) ;
        }

        for( i = 0 ; i <= N ; i ++ )
            if( count[i] > 0 ) printf( "%d:%d\n" , i , count[i] ) ;
    }
    return 0 ;
}

2，tarjan离线

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;

struct type
{
    int  end , next ;
    //int  w ;
} ;

const int MAXN = 20005 ;

int   N , M ;
type  edge[MAXN*2] , qedge[MAXN*25] ;
int   head[MAXN] , qhead[MAXN] ;
int   ind[MAXN]  , vis[MAXN]   ;
int   father[MAXN] , ans[MAXN] ;
int   Count , qcnt             ;

void  addedge( int start , int end )
{
    edge[Count].end  = end         ;
    //edge[Count].w    = w           ;
    edge[Count].next = head[start] ;
    head[start]      = Count ++    ;
}

void  qaddedge( int start , int end )
{
    qedge[qcnt].end  = end          ;
    //qedge[qcnt].w    = w            ;
    qedge[qcnt].next = qhead[start] ;
    qhead[start]     = qcnt ++      ;
}

int  find( int x )
{
    if( father[x] == -1 ) return x ;
    father[x] = find( father[x] )  ;
    return father[x]               ;
}

void  tarjan( int start )
{
    int  i , j ;
    vis[start] = 1 ;
    for( i = qhead[start] ; i != -1 ; i = qedge[i].next )
    {
        if( vis[qedge[i].end] )
        {
            int  temp = find( qedge[i].end ) ;
            ans[temp] ++ ;
        }
    }

    for( i = head[start] ; i != -1 ; i = edge[i].next )
    {
        if( !vis[edge[i].end] )
        {
            tarjan( edge[i].end ) ;
            father[edge[i].end] = start ;
        }
    }
}

int  main()
{
    int   i , j ;
    int   start , end , num ;
    char  ch  ;

    while( scanf( "%d" , & N ) != EOF )
    {
        memset( head   , -1 , sizeof( head   ) ) ;
        memset( qhead  , -1 , sizeof( qhead  ) ) ;
        memset( father , -1 , sizeof( father ) ) ;
        memset( ind    ,  0 , sizeof( ind    ) ) ;
        memset( vis    ,  0 , sizeof( vis    ) ) ;
        memset( ans    ,  0 , sizeof( ans    ) ) ;
        Count = 0 ; qcnt = 0 ;

        for( i = 1 ; i <= N ; i ++ )
        {
            scanf( "%d:(%d)" , & start , & num ) ;
            while( num -- )
            {
                scanf( "%d" , & end ) ;
                ind[end] ++ ;
                addedge( start , end ) ;
                addedge( end , start ) ;
            }
        }

        scanf( "%d" , & M ) ;
        while( M -- )
        {
            while( ch = getchar() )
                if( ch == '(' )
                {
                    scanf( "%d%d" , & start , & end ) ;
                    ch = getchar() ;
                    break ;
                }
            qaddedge( start , end ) ;
            qaddedge( end , start ) ;
        }

        for( i = 1 ; i <= N ; i ++ )
            if( ind[i] == 0 )
            {
                tarjan( i ) ;
                break ;
            }

        for( i = 0 ; i <= N ; i ++ )
            if( ans[i] ) printf( "%d:%d\n" , i , ans[i] ) ;
    }
    return 0 ;
}