poj2186 解题报告

题意:有一些奶牛,他们之间有互相崇拜的关系,并且这个关系是有传递性的,求被所有奶牛崇拜的奶牛数量;

题解:先用强连通缩点,把强连通分量缩成一个点,强连通中的点必然是互相崇拜的,然后再缩点后的图中找

到出度为零的点,如果这些点的数量大于一,那么必然没有解,因为这些点直接没有互相崇拜关系,如果只有

一个点,那么求出这个点对应的强连通分量里面的点的个数就是答案了;

代码搓了点:

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

const int MAXN = 10005 ;
const int MAXM = 50005 ;

struct type
{
    int  end , next ;
} ;

type  edge[MAXM] ;
int   head[MAXN] , low[MAXN] , dfn[MAXN] , stack[MAXN] ;
int   vis[MAXN] , Count , M , N , m  ;

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

void  dfs( int k , int lay , int &cnt )
{
    vis[k] = 1 ;
    low[k] = lay ;
    dfn[k] = lay ;
    stack[++m] = k ;
    for( int i = head[k] ; i != -1 ; i = edge[i].next )
    {
        if( !vis[edge[i].end] ) dfs( edge[i].end , ++ lay , cnt ) ;
        if( vis[edge[i].end] == 1 ) low[k] = min( low[k] , low[edge[i].end] ) ;
    }
    if( dfn[k] == low[k] )
    {
        ++ cnt ;
        do
        {
            low[stack[m]] = cnt ;
            vis[stack[m]] = 2 ;
        }while(stack[m--] != k ) ;
    }
}

int   tarjan()
{
    int  cnt = 0 , lay = 0 ;
    m = 0 ;
    memset( vis , 0 , sizeof( vis ) ) ;
    memset( low , 0 , sizeof( low ) ) ;
    for( int i = 1 ; i <= N ; i ++ )
        if( !vis[i] ) dfs( i , lay , cnt ) ;
    return cnt ;
}

int  main()
{
    int  outdex[MAXN] , num[MAXN] , ans = -1 ;
    int  i , j ;
    memset( head , -1 , sizeof( head ) ) ;
    memset( num  ,  0 , sizeof( num  ) ) ;
    memset( outdex , 0 , sizeof( outdex ) ) ;
    Count = 0 ;
    scanf( "%d%d" , & N , & M ) ;
    while( M -- )
    {
        int start , end ;
        scanf( "%d%d" , & start , & end ) ;
        addedge( start , end ) ;
    }
    int  temp = tarjan() ;
    for( i = 1 ; i <= N ; i ++ )
    {
        num[low[i]] ++ ;
        for( j = head[i] ; j != -1 ; j = edge[j].next )
        {
            if( low[i] != low[edge[j].end] ) outdex[low[i]] ++ ;
        }
    }
    for( i = 1 ; i <= temp ; i ++ )
        if( ans == -1 ){
            if( outdex[i] == 0 )
            ans = i ;
        }
        else if( outdex[i] == 0 ) ans = -2 ;
    if( ans == -2 ) cout << 0 << endl ;
    else cout << num[ans] << endl ;
    return 0 ;
}