首页 > 8.16 19点阿里笔试
头像
牛客523835105号
编辑于 2021-08-17 12:01
+ 关注

8.16 19点阿里笔试

第一题:简单的字符串分割,相信大家都a了
第二题:主要思想并查集,代码如下:
import java.util.*;

public class Main {
    static int[] parent;
    static int[] size;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = sc.nextInt();
        }
        while (m-- > 0){
            int t = sc.nextInt();
            int x = sc.nextInt()-1;
            int y = sc.nextInt()-1;
            if(t == 1){
                if(!isConnected(x,y)){
                    System.out.println((find(x)+find(y)+2)^Math.abs(size[find(x)]-size[find(y)]));
                    union(x,y);
                }
            }else {
                if(isConnected(x,y))
                    System.out.println("YES");
                else
                    System.out.println("NO");
            }
        }
    }

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

    public static boolean isConnected(int p,int q){
        return find(p) == find(q);
    }

    public static void union(int p,int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot)
            return;

        if(pRoot < qRoot){
            parent[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
        }else {
            parent[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
        }
    }
}


全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐