hdu 1213 How Many Tables ([kuangbin带你飞]专题五 并查集)

点击打开链接

给你一个数T，代表有几组数据，然后给你两个数m and n，表示有m个同学，

有n种关系，x 和 y 是同学，求最少需要多少桌子，

样例解释：

5 3

1 2

2 3

4 5

1和2是同学， 2和3是同学， 4和5是同学

所以只需要两张桌子，以为有两块（1，2，3）和（4，5）；

所以就有两块

解题思路：

纯的并查集，套模板就行，

直接上代码，

ps：我第一次是CE了，因为把下面的代码是AC的，CE是因为rank数组没用着还是咋回事，

我也不太清楚，有知道的可以告诉我哦，我只是把代码的一部分注释了就AC了，

/**
2015 - 09 - 18 晚上
Author: ITAK

Motto:

今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
**/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long LL;
const int maxn = 30005;
const double eps = 1e-7;

struct node
{
    int x, y;
} arr[maxn];

int rank[maxn], fa[maxn], sum[maxn];
///基本上是模板
void Init(int x)
{
    for(int i=1; i<=x; i++)
    {
        fa[i] = i;
        ///rank[i] = 0;
        sum[i] = 1;
    }
}

int Find(int x)
{
    if(fa[x] != x)
        fa[x] = Find(fa[x]);
    return fa[x];
}

void Union(int x, int y)
{
    int fx = Find(x), fy = Find(y);
    if(fx == fy)
        return;
    /**
    if(rank[fx] > rank[fy])
        fa[fy] = fx, sum[fx] += sum[fy];
    else
    {
        fa[fx] = fy;
        if(rank[fx] == rank[fy])
            rank[fy]++;
        sum[fy] += sum[fx];
    }
    **/
    if(fx != fy)
        fa[fy] = fa[fx];
}

int main()
{
    int T, m, n, x, y;
    cin>>T;
    while(T--)
    {
        int cnt = 0;
        cin>>m>>n;
        Init(m);
        while(n--)
        {
            cin>>x>>y;
            Union(x, y);
        }
        for(int i=1; i<=m; i++)
            if(fa[i] == i)
            cnt++;
        cout<<cnt<<endl;
    }
    return 0;
}