2753473 2008-02-17 16:25:45 Accepted 2740 C++ 00:00.00 436K C.D. 世界上最郁闷的事情，不是连续五个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;}

评论