题解 | #小团的配送团队#

小团的配送团队

http://www.nowcoder.com/questionTerminal/13218137bf64448d9ef485ca219377bf

package com._2021._02;
import java.util.*;

/**
 * @author Jiang锋时刻
 * @create 2021-08-09 15:54
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < m; i++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            uf.union(v1, v2);
        }
        System.out.println(uf.size());
        /**
         * 之前使用的是HashMap, 会出现乱序的情况
         */
        TreeMap<Integer, ArrayList<Integer>> map = new TreeMap<>();
        for (int i = 0; i <= n; i++) {
            int v = uf.parent[i];
            if (map.get(v) == null) {
                map.put(v, new ArrayList<>());
            }
            map.get(v).add(i);
        }

        for (int key: map.keySet()) {
            if (key == 0) {
                continue;
            }
            int size = map.get(key).size();
            for (int j = 0; j < size; j++) {

                System.out.print(map.get(key).get(j) + " ");
            }
            System.out.println();
        }
    }
}

class UnionFind {
    public int[] parent;
    public int count;
    public UnionFind(int n) {
        count = n;
        parent = new int[n + 1];
        for(int i = 1; i <= n; i++){
            parent[i] = i;
        }
    }

    public int find(int x) {
        while(parent[x] != x){
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    /**
     * 之前只进行的合并, 并没有想到将大的编号放在小的编号下面
     * @param x
     * @param y
     */
    public void union(int x, int y) {
        if(x == y) return;
        int rootX = find(x);
        int rootY = find(y);
        if(rootX == rootY) return;
        // 将节点编号大的合并到节点编号小的节点下面
        if(rootX < rootY){
            for(int i = 0; i < parent.length; ++i){
                if(parent[i] == rootY)
                    parent[i] = rootX;
            }
        }else{
            for(int i = 0; i < parent.length; ++i) {
                if(parent[i] == rootX)
                    parent[i] = rootY;
            }
        }
        count --;
    }
    public int size(){
        return count;
    }
}
全部评论

相关推荐

#牛客AI配图神器#和波主熟的朋友们都知道,波主真的很挺贪玩的哈哈哈哈很少看八股,也不爱看。。可能你们现在拷打波主八股会支支吾吾...回想我的面试,似乎都是围绕着我会的地方问,大概是最近和宿佬还有学长学到的引导面试罢...注意,此文只适合对面试技巧提升,并不是说可以不学八股啊喂!!回忆本人的面试经验,面试官刚拿到你的简历,对你是一无所知的,那其实他会根据印象深的东西对你进行提问,所以我们在简历方面可以做一个引导。面试开头是很正常的自我介绍,很多人会觉得随便说一下就好,但其实我们可以在这里也做一个引导的,而且多说一点也可以给面试官时间看你的简历,所以这里也可以准备一下。然后就是具体提问了,对实习...
nokotan:佬tql,还很谦虚。个人决定佬说得很对,要有意把面试官提问引导到简历项目上,但前提是自己对项目一定要熟悉。项目的需求背景、难点痛点、已有方案的不足、解决方案的实现都得有认知,虽然我们实习大多数是打杂,但是不影响我们偷文档学业务。只要能把上面几个点做到自圆其说,那基本就有6、7成把握了
点赞 评论 收藏
分享
learYuan:🐕看了都摇头
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务