連通分支

#include <stdio.h>

const int LEN = 10005;

int flag; //強(qiáng)連通分支標(biāo)號(hào)

struct HEAD //結(jié)點(diǎn)頭
{
    int state; //搜索處在的狀態(tài)
    int flag; //強(qiáng)連通分支標(biāo)號(hào)
    int count; //結(jié)點(diǎn)的出度

    int next;
    int last;
};
HEAD head1[LEN]; //原圖
HEAD head2[LEN]; //逆圖
HEAD head3[LEN]; //縮點(diǎn)后的圖

int time[LEN]; //存儲(chǔ)結(jié)點(diǎn)
int next_time;

struct //模擬的內(nèi)存
{
    int num;
    int next;
}node[LEN*20];
int next_node;

int hash[LEN];

void init ( int n ) //初始化
{

    for ( int i=0; i<n; i++ )
    {
        hash[i] = 0;
    }
    flag = 0;
    next_node = 0;
    next_time = 0;
}

void init_head ( int n, HEAD *head ) //初始化鏈表
{

    for ( int i=0; i<n; i++ )
    {
        head[i].count = 0;
        head[i].flag = -1;
        head[i].next = -1;
        head[i].state = 0;
    }
}

void ins ( int a, int b, HEAD *head ) //插入一條邊
{

    node[next_node].next = -1;
    node[next_node].num = b;
    next_node ++;

    if ( head[a].next==-1 )
    {
        head[a].next = next_node-1;
    }
    else
    {
        node[ head[a].last ].next = next_node-1;
    }
    head[a].last = next_node-1;
    head[a].count ++;
}

//極度簡(jiǎn)化的堆棧
int stack[LEN][2];
int top;

inline void push( int a[] ) //出堆棧
{

    top ++;
    stack[top][0] = a[0];
    stack[top][1] = a[1];
}

inline int isempty ()
{

    return top<0 ? 1:0;
}

void mark ( int s, HEAD *head ) //對(duì)原圖進(jìn)行深搜
{

    int i;
    int now[2];
    top = -1;

    now[0] = s;
    now[1] = head[s].next;
    push ( now );
    head[ now[0] ].state = 1;
    while ( !isempty () )
    {
        now[0] = stack[top][0];
        now[1] = stack[top][1];
        for ( i=now[1]; i!=-1; i=node[i].next )
        {
            if ( !head[ node[i].num ].state )
            {
                stack[top][1] = node[i].next;
                now[0] = node[i].num;
                now[1] = head[ node[i].num ].next;
                push ( now );
                head[ now[0] ].state = 1;
                break;
            }
        }
        if ( i==-1 )
        {
            head[ now[0] ].state = 2;
            time[ next_time++ ] = now[0];
            top --;
        }
    }
}

void ser ( int s, HEAD *head )
{

    int i;
    int now[2];
    top = -1;

    now[0] = s;
    now[1] = head[s].next;
    push ( now );
    head[ now[0] ].state = 1;
    head[ now[0] ].flag = flag;
    while ( !isempty () )
    {
        now[0] = stack[top][0];
        now[1] = stack[top][1];
        for ( i=now[1]; i!=-1; i=node[i].next )
        {
            if ( !head[ node[i].num ].state )
            {
                stack[top][1] = node[i].next;
                now[0] = node[i].num;
                now[1] = head[ node[i].num ].next;
                push ( now );
                head[ now[0] ].flag = flag;
                head[ now[0] ].state = 1;
                break;
            }
        }
        if ( i==-1 )
        {
            head[ now[0] ].state = 2;
            top --;
        }
    }
}

void work ( int n, HEAD *h1, HEAD *h2, HEAD *h3 )
{

    for ( int i=0; i<n; i++ )
    {
        if ( !h1[i].state )
        {
            mark ( i, h1 );
        }
    }
    for ( int i=next_time-1; i>=0; i-- )
    {
        if ( !h2[ time[i] ].state )
        {
            ser ( time[i], h2 );
            flag ++;
        }
    }
    //找極大強(qiáng)連通分支

    init_head ( flag, h3 );
    for ( int i=0; i<n; i++ )
    {
        for ( int j=h2[i].next; j!=-1; j=node[j].next )
        {
            if ( h2[i].flag!=h2[ node[j].num ].flag )
            {
                ins ( h2[ node[j].num ].flag, h2[i].flag, h3 );
            }
        }
    }
    //縮點(diǎn)

    for ( int i=0; i<flag; i++ )
    {
        if ( !h3[i].count )
        {
            for ( int j=0; j<n; j++ )
            {
                if ( h2[j].flag==i )
                {
                    hash[j] = 1;
                }
            }
        }
    }
    for ( int i=0; i<n; i++ )
    {
        if ( hash[i] )
        {
            printf ( "%d ", i+1 );
        }
    }
    printf ( "\n" );
}

int main ()
{

    int n, m;
    int a, b;
    while ( scanf ( "%d", &n )!=EOF && n )
    {
        scanf ( "%d", &m );
        init ( n );
        init_head ( n, head1 );
        init_head ( n, head2 );
        for ( int i=0; i<m; i++ )
        {
            scanf ( "%d%d", &a, &b );
            if ( a!=b )
            {
                ins ( a-1, b-1, head1 );
                ins ( b-1, a-1, head2 );
            }
        }
        work ( n, head1, head2, head3 );
    }
    return 0;
}