POJ 2236 The Suspects HDU 1213 How Many Tables

The Suspects

n个人（0 ~ n-1）m个小组

起初0是嫌疑人，与0共组的人都是嫌疑人，与嫌疑人共组的人也都是嫌疑人

问有多少嫌疑人

Code(并查集模板)

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 30005;

int pre[N];
int n, m;

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

int found(int x)
{
    if(x != pre[x])
        pre[x] = found(pre[x]);
    return pre[x];
}

void unite(int a, int b)
{

    int x = found(a);
    int y = found(b);
    if(x != y)
//        x = pre[y];///可笑...
        pre[y] = x;
    return ;
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        if(n == 0 && m == 0)
            break;
        init();
        while(m--)
        {
            int tem, t, first;
            scanf("%d", &tem);
            scanf("%d", &first);
            while(--tem)
            {
                scanf("%d", &t);
                unite(first, t);
            }
        }
        int standard = found(0);
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            if(found(i) == standard)
                ans++;
        }
        cout << ans << '\n';
    }
}

How many tables

n个人（1~n）m个关系

认识的人坐一桌，最少需要几桌

我认识我朋友，我朋友认识他三姨夫，那么我和我朋友的三姨夫彼此认识？？？

Link http://acm.hdu.edu.cn/showproblem.php?pid=1213

Code（并查集模板）

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1005;

int pre[N];
bool vis[N];
int n, m;

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

int found(int x)
{
    if(x != pre[x])
        pre[x] = found(pre[x]);
    return pre[x];
}

void unite(int a, int b)
{
    int x = found(a);
    int y = found(b);
    if(x != y)
        pre[x] = y;
    return ;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset(vis, 0, sizeof(vis));
        scanf("%d%d", &n, &m);
        init();///最初在主函数里忘写了，后来有写在n被赋值之前...
        int there, here;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d", &there, &here);
            unite(there, here);
        }
        int ans = 0;
        for(int i = 1; i <= n; ++i)
            if(!vis[ found(i) ])
            {
                vis[ found(i) ] = 1;
                ans++;
            }
        cout << ans << '\n';
    }
    return 0;
}