分享一下自己顺丰第二题并查集代码

import java.util.*;

class Node {
    int val = 0;
    int father = -1;
    boolean flag = false;// 避免算入未学习过的语言

    public Node(int val, int father) {
        this.val = val;
        this.father = father;
    }

    int getFather() {
        flag = true;
        if (father == -1) return val;
        else {
            int temp = Main.nodes[father].getFather();
            father = temp;
            return father;
        }
    }

    void set(int target) {
        int temp = getFather();
        target = Main.nodes[target].getFather();
        if (temp != target) {
            Main.nodes[temp].father = target;
        }
        if (target != val) father = target;
    }
}

class Main {
    public static Node[] nodes;


    public static void main(String[] args) {
        HashSet<Integer> integers = new HashSet<>();
        Scanner scanner = new Scanner(System.in);
        int n, m, k;
        Map<Integer, List<Integer>> map = new HashMap<>();
        n = scanner.nextInt();
        m = scanner.nextInt();
        k = scanner.nextInt();
        nodes = new Node[m + 1];
        for (int i = 0; i <= m; i++) nodes[i] = new Node(i, -1);
        for (int i = 0; i < k; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            List<Integer> list = map.getOrDefault(a, new ArrayList<>());
            list.add(b);
            map.put(a, list);
        }

        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            for (int i : entry.getValue()) {
                int temp = entry.getValue().get(0);
                nodes[i].set(temp);
            }
        }



        for (Node node : nodes) {
            if (node.flag) {
                integers.add(node.getFather());

            }
        }
        int res = n - map.size() + integers.size() - 1;
        if (n == 2 && integers.size() == 0) res = 2;
        System.out.println(res);
    }
}

其实思路很简单,就是记录每个人会的语言并记录，形成并查集，最后结果为未连通的树（语言）-1+不会语言的人，这里需要考虑的特殊条件是如果两人都没有学习过语言，返回值会是1，应该是2（我在这个边界值卡了20分钟），虽然AC了，但是不一定保证没有bug，欢迎指正。