世界上最郁闷的事情，不是连续五个WA，而是连续莫名其妙的WA，却不知道错在哪里；比这更郁闷的事情，是改动之后的连续五个AC，却发现再也找不到刚才究竟错在哪里……

遥想当年，浙大初赛时，雄姿英发；谈笑间，代码灰飞烟灭。故题重做，多情应笑我，迟来三年。卡了近三年的题目，回过头来再看也是一道简单题。

求图是否为连通生成树。预处理边数M，然后用并查集检查一下是否有回路，马上就可以解决。

因为满足生成树的情况下，M恒等于点数N-1，所以在预处理后就不需要考虑是否所有点都能够被访问。开始的时候写了一个BFS算法，遍历，结果失败。（我果然还是比较菜……= =）

#include <cstdio>
#include <string>

int N, M, p[1001], num[1001];

int init ();
void init_set ();
int find_set ( int );
int union_set ( int, int );

int main ()
{
    //freopen ( "in.txt", "r", stdin );
    while ( init () )
    {
    }
    return 0;
}

void init_set ()
{
    int i;
    for ( i = 1; i <= N; i ++ )
    {
        p[i] = i;
        num[i] = 1;
    }
}

int find_set ( int x )
{
    int pre = x;
    while ( p[pre] != pre )
    {
        pre = p[pre];
    }
    int root = pre;
    while ( x != root )
    {
        int t = p[x];
        p[x] = root;
        x = t;
    }
    return root;
}

int union_set ( int x1, int x2 )
{
    int p1 = find_set ( x1 );
    int p2 = find_set ( x2 );
    if ( p1 == p2 )
    {
        return 0;
    }
    if ( num[p1] > num[p2] )
    {
        num[p2] += num[p1];
        p[p1] = p2;
    }
    else
    {
        num[p1] += num[p2];
        p[p2] = p1;
    }
    return 1;
}

int init ()
{
    scanf ( "%d %d", &N, &M );
    if ( N == 0 )
        return 0;
    int i, ac = 1;
    if ( N != M + 1 )
    {
        printf ( "No\n" );
        for ( i = 0; i < M; i ++ )
        {
            int x, y;
            scanf ( "%d %d", &x, &y );
        }
    }
    else
    {
        init_set ();
        for ( i = 0; i < M; i ++ )
        {
            int x, y;
            scanf ( "%d %d", &x, &y );
            if ( union_set ( x, y ) == 0 )
            {
                ac = 0;
            }
        }
        if ( ac )
        {
            printf ( "Yes\n" );
        }
        else
        {
            printf ( "No\n" );
        }
    }
    return N;
}

评论