CodeForces 277A Learning Languages (并检查集合)

A. Learning Languages

time limit per test：2 seconds

memory limit per test：256 megabytes

The "BerCorp" company has got
n employees. These employees can use m approved official languages for the formal correspondence. The languages are numbered with integers from
1 to m. For each employee we have the list of languages, which he knows. This list could be empty, i. e. an employee may know no official languages. But the employees are willing to learn
any number of official languages, as long as the company pays their lessons. A study course in one language for one employee costs
1 berdollar.

Find the minimum sum of money the company needs to spend so as any employee could correspond to any other one (their correspondence can be indirect, i. e. other employees can help out translating).

Input

The first line contains two integers
n and m (2 ≤ n, m ≤ 100) — the number of employees and the number of languages.

Then n lines follow — each employee's language list. At the beginning of the
i-th line is integer
k_i (0 ≤ k_i ≤ m) — the number of languages the
i-th employee knows. Next, the
i-th line contains k_i integers —
a_ij (1 ≤ a_ij ≤ m) — the identifiers of languages the
i-th employee knows. It is guaranteed that all the identifiers in one list are distinct. Note that an employee may know zero languages.

The numbers in the lines are separated by single spaces.

Output

Print a single integer — the minimum amount of money to pay so that in the end every employee could write a letter to every other one (other employees can help out translating).

Sample test(s)

Input

Output

Input

Output

Input

Output

Note

In the second sample the employee
1 can learn language 2, and employee
8 can learn language 4.

In the third sample employee
2 must learn language 2.

题目链接：http://codeforces.com/problemset/problem/277/A

题目大意：n个员工。m种语言。每一个员工会k种语言，问总共还要学习多少语言，能够让每两个员工能够直接或者间接交流

题目分析：非常明显的并查集问题，注意当k等于0时，该员工必学一门语言。具体见程序凝视

#include <cstdio>

#include <cstring>

int a[105], fa[105];

void UF_set()

{

    for(int i = 0; i < 105; i++)

        fa[i] = i;

}

int Find(int x)

{

    return x == fa[x] ?

x : fa[x] = Find(fa[x]);

}

void Union(int a, int b)

{

    int r1 = Find(a);

    int r2 = Find(b);

    if(r1 != r2)

        fa[r2] = r1;

}

int main()

{

    int n, m, cnt = 0, ans = 0;   //ans表示理论上须要学习的人数,cnt表示没人学的

    scanf("%d %d", &n, &m);

    memset(a, 0, sizeof(a));

    UF_set();

    for(int i = 0; i < n; i++)

    {

        int k, fir, next;

        scanf("%d", &k);

        if(k == 0)      //若一门语言都不会。则必要学一门

        {

            ans++;

            continue;

        }

        scanf("%d", &fir);

        a[fir] ++;

        for(int i = 1; i < k; i++)

        {

            scanf("%d", &next);

            a[next]++;

            Union(fir, next);

        }

    }

    for(int i = 1; i <= m; i++)

    {

        if(a[i] == 0)       //记录没人学的

            cnt++;

        if(fa[i] == i)      //记录集合个数

            ans++;

    }

    //没人学的必定自成一个集合，我们要把它减去，由于既然没一个人学

    //它就不须要再被学，若ans等于m说明每两个人之间不能交流。则每人都要学习

    //一门语言，否则拿集合个数减去没人学的语言个数再减1，这里减1的含义是

    //随意n个集合，n－1条线就能将其连通

    printf("%d\n", (cnt == m) ? n : ans - cnt - 1);

}

秒客网

CodeForces 277A Learning Languages (并检查集合)

相关文章