8.25今日头条第一题

8.25今日头条第一题

笔试的时候没做出来，后来参考网上的讨论，采用Union-Find算法。试了下测试用例，输出正确。如果有人发现有哪里不合适，请给出建议

import java.util.*;

public class Toutiao01 {

    /**
     * 连通分量数
     */
    private int count;

    /**
     * 每个数所属的连通分量
     */
    private int[] id;

    /**
     * 初始化时，n个点有n个分量
     * @param n n个点
     */
    public Toutiao01(int n) {
        count = n;
        id = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            id[i] = i;
        }
    }

    /**
     *
     * @return 返回连通分量数
     */
    public int getCount() {
        return count;
    }

    /**
     * @param x
     * @return 返回x所属的连通分量
     */
    public int find(int x) {
        return id[x];
    }

    /**
     * 连接p,q(将q的分量改为p所在的分量)
     * @param p
     * @param q
     */
    public void union(int p, int q) {
        int pId = find(p);
        int qId = find(q);
        for (int i = 1; i < id.length; ++i) {
            if (find(i) == qId) {
                id[i] = pId;
            }
        }
        --count; //记得每进行一次连接，分量数减“1”
    }

    /**
     * 判断p,q是否连接，即是否属于同一分量
     * @param p
     * @param q
     * @return p,q属于同一分量，返回true， 否则返回false
     */
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n <= 0 || n >= 100000) {
            System.out.println(0);
            return;
        }
        /**
         * 用来保存初始输入的联通分量
         */
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 1; i <= n; ++i) {
            Set<Integer> set = new HashSet<>();
            int num;
            while ((num = sc.nextInt()) != 0) {
                set.add(num);
            }
            if (set.size() != 0)
                map.put(i, set);
        }

        Toutiao01 toutiao = new Toutiao01(n);
        Set<Integer> keys = map.keySet();
        for (Iterator<Integer> iterator = keys.iterator(); iterator.hasNext(); ) {
            Integer key = iterator.next();
            Set<Integer> values = map.get(key);
            for (Iterator<Integer> it = values.iterator(); it.hasNext(); ) {
                Integer value = it.next();
                if (toutiao.connected(key, value))
                    continue;
                toutiao.union(key, value);
            }
        }

        System.out.println(toutiao.count);
    }
}

算法参考文章(参考第一种方法)
https://www.cnblogs.com/SeaSky0606/p/4752941.html