A - Learning Languages CodeForces - 277A（并查集 Java实现）

╰半橙微兮° 2024-04-17 19:58 59阅读 0赞

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 ki (0 ≤ ki ≤ m) — the number of languages the i-th employee knows. Next, the i-th line contains ki integers — aij (1 ≤ aij ≤ 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).

Examples  
inputCopy  
5 5  
1 2  
2 2 3  
2 3 4  
2 4 5  
1 5  
outputCopy  
0  
inputCopy  
8 7  
0  
3 1 2 3  
1 1  
2 5 4  
2 6 7  
1 3  
2 7 4  
1 1  
outputCopy  
2  
inputCopy  
2 2  
1 2  
0  
outputCopy  
1  
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.

**因为在秋招笔试题目中遇到了这个题的变形，所以在这里记录一下**

> 并查集是一种可以快速判断两个节点连通性的数据结构，已经有很多关于并查集的介绍了，这里就不再赘述了。并查集用到的核心数据结构和方法是：  
> id数组：id\[i\]表示i所属的集合  
> init方法：对id数组进行初始化，初始，令id\[i\]=i,每个元素属于一个单独的集合  
> find(int p)方法：找到p所属的集合  
> union(int p, int q):将p，q节点及以p,q为根的节点合并到一个集合中，

注意：这道题目本质上就是使用并查集来做，但是明确集合合并的是语言而不是人，此外还要一个标记数组统计那些没有人说的语言，由于这些构成了一个集合，所以必须要统计最后进行排除！

import java.util.Arrays;
    import java.util.Scanner;
    
    //所/有人都不会任何语言的时候，答案是n而不是n-1。
    public class LearningLanguages {
    
        static int n, m;
        /*
        id数组
        * */
        static int[] id = new int[110], cnt = new int[110];
    
        private static void init(int m) {
            for (int i = 1; i <= m; i++) {
                id[i] = i;
            }
        }
    
        private static int find(int p) {
            return id[p];
        }
    
        private static void union(int p, int q) {因为在秋招笔试题目中遇到了这个题的变形，所以在这里记录一下
            int pID = find(p);
            int qID = find(q);
            if (pID == qID) return;
            for (int i = 1; i <= m; i++) {
                if (id[i] == pID) {
                    id[i] = qID;
                }
            }
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) {
                n = sc.nextInt();
                m = sc.nextInt();
                init(m);
                Arrays.fill(cnt, 0);
                //disjointCnt表示不相交集合的个数
                int disjointCnt = 0, zeroCnt = 0;
                for (int i = 0; i < n; i++) {
                    int k = sc.nextInt();
                    if (k == 0) {
                        disjointCnt++;
                        continue;
                    }
                    int first = sc.nextInt();
                    cnt[first]++;
                    for (int j = 1; j < k; j++) {
                        int next = sc.nextInt();
                        cnt[next]++;
                        if (find(first) != find(next)) {
                            union(first, next);
                        }
                    }
                }
                for (int i = 1; i <= m; i++) {
                    if (cnt[i] == 0) zeroCnt++;
                    if (find(i) == i) disjointCnt++;
                }
                disjointCnt -= zeroCnt;
                //注意在上面的循环中，由于初始化的情况，ans将空集合也统计进去了，所以最后是需要
                //对于n个独立的点，只需要n-1条边就够了，注意当n个人都不会任何一种语言时，值为n
                System.out.println(zeroCnt == m ? n : disjointCnt - 1);
            }
        }
    }