hdu1232 通畅工程（并查集）

hdu1232 畅通工程（并查集）

本文出自：http://blog.csdn.net/svitter

原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=1232

题意：题意大可不必叙述了吧。。典型的并查集问题。

什么是并查集？

并查集就是将同一集合的东西放到同一集合里面。最简单的理解方式就是一根香肠拉出来，连接的全在一起，最后数数有几串香肠就是几个并查集。= =

过程：我就是一纯逗逼。。有个join函数不用自己乱写- =用了STL的stack莫名奇妙的超空间脑子愣是不转，后来发现最简单的问题就是我根本没有考虑到输入的次序然后到底怎么分的集合。给自己SB的心态深深地跪了。。终于看明白了JOIN函数，也算是好好巩固了并查集吧TAT

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int fa[1010];
bool vis[1010];
int m, n;
int cur;
int tmp;

void init()
{
    for(int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
}

int find(int v)
{
    if(fa[v] == v)
        return v;
    else
        return find(fa[v]);
}

int is_same(int x, int y)
{
    return (find(x) == find(y));
}

void join(int x, int y)
{
    int fx = find(x), fy = find(y);
    if(fx != fy)
        fa[fx] = fy;
}

void ace()
{
    int pre, next;
    int i;
    int num;
    while(1)
    {
        scanf("%d", &n);
        if(n == 0)
            break;
        scanf("%d", &m);
        init();
        memset(vis, 0, sizeof(vis));
        num = -1;

        for(i = 1; i <= m; i++)
        {
            scanf("%d%d", &pre, &next);
            //judge
            join(pre, next);
        }

        for(i = 1; i <= n; i++)
        {
            vis[find(i)] = 1;
        }

        for(i = 0; i <= n; i++)
        {
            if(vis[i])
                num++;
        }

        printf("%d\n", num);
    }
}

int main()
{
    ace();
    return 0;
}