Codeforces 278C Learning Languages(并查集) - c++编程基础

题意抽象出来就是求联通块的个数吧，然后添加最少边使图联通。

注意所有人都不会任何语言的时候，答案是n而不是n-1。

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define FF(i, a, b) for(int i=a; i=b; i--)  
#define REP(i, n) for(int i=0; i lg[maxn];  
set :: iterator it;  
  
int findset(int x) { return x == fa[x]   x : fa[x] = findset(fa[x]); }  
  
bool check(int i, int j)  
{  
    for(it=lg[i].begin(); it!=lg[i].end(); it++)  
        if(lg[j].find(*it) != lg[j].end()) return true;  
    return false;  
}  
  
int main()  
{  
    scanf("%d%d", &n, &m);  
    int cnt = 0;  
    FF(i, 1, n+1)  
    {  
        fa[i] = i;  
        scanf("%d", &k);  
        if(k == 0) cnt++;  
        while(k--)  
        {  
            scanf("%d", &x);  
            lg[i].insert(x);  
        }  
    }  
    if(cnt == n)  
    {  
        printf("%d\n", n);  
        return 0;  
    }  
    FF(i, 1, n+1) FF(j, i+1, n+1) if(check(i, j))  
    {  
        int x = findset(i), y = findset(j);  
        if(x != y) fa[x] = y;  
    }  
    int ans = 0;  
    FF(i, 1, n+1) if(fa[i] == i) ans++;  
    printf("%d\n", ans-1);  
    return 0;  
}