数据结构作业——游戏分组

发表于 分类于 阅读次数：

游戏分组
时间限制: 1000 ms
内存限制: 128 MB

为了活跃蒜厂的工作气氛，促进彼此间的友谊，蒜头君决定挑个阳光明媚的周末，带领同学们一起玩游戏。一共有 n 位同学要参加，编号为 0 到 n - 1。蒜头君要对这些同学进行分组，而且蒜头君已经知道哪两个同学之间是好友关系。为了让同学们都玩得开心，蒜头君决定最终的分组方案要将所有好友组合都被分在一组。
蒜头君现在知道有 m 对好友关系，需要注意的是，有可能一个同学有很多个好友，也有可能一个同学没有好友。为了让游戏更有趣，蒜头君希望最后分出的组数尽可能多。你能帮蒜头君算出来最多可以分成多少组么？

输入格式：
第一行输入两个数 n 和 m，1 ≤ n, m ≤ 1000000。
接下来输入 m 行，每行输入两个数 a 和 b，表示编号 a 和编号 b 的同学是好友关系，0 ≤ a, b ≤ n - 1。

输出格式：
输出为一行，表示最多可以分成多少组。

输入样例:

1
2
3
5 2
0 2
2 3

输出样例:

1
3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h>
#include <stdlib.h>

int *father, *size;

int find(int n)
{
    if(father[n] != n)
        father[n] = find(father[n]);    //路径压缩
    return father[n];
}

int merge(int a, int b)
{
    int roota = find(a), rootb = find(b);
    if(roota == rootb)
        return 0;
    if(size[roota] > size[rootb])
    {
        int temp = roota;
        roota = rootb;
        rootb = temp;
    }
    father[roota] = rootb;    //启发式合并（按集合大小）
    size[rootb] += size[roota];
    return 1;
}

void init(int n)
{
    father = (int *)malloc(sizeof(int) * n);
    size = (int *)malloc(sizeof(int) * n);
    for(int i = 0; i < n; ++i)
    {
        father[i] = i;
        size[i] = 1;
    }
}

int main()
{
    int n, m, a, b, num;
    scanf("%d%d", &n, &m);
    init(n);
    num = n;
    while(m--)
    {
        scanf("%d%d", &a, &b);
        if(merge(a, b))
            num--;
    }
    printf("%d", num);
    return 0;
}