java MLE咋搞呀,其他的都对

P3367 【模板】并查集

xxb123 @ 2021-01-26 22:13:45


import java.util.Scanner;

public class DisjointSet {
    public static void main(String[] args) {
        DisjointSet m = new DisjointSet();
        m.handleInput();
    }
    int m=0;
    int n=0;
    public void handleInput() {
        Scanner in = new Scanner(System.in);
        if (in.hasNext()) {
            m = in.nextInt();
            n = in.nextInt();}
        int[] parent = new int[m];
        int[] rank = new int[m];
        int[][] a = new int[n][2];
        int[] q = new int[n];
        initialise(parent,rank);
        for(int i=0;i<n;i++) {
            q[i] = in.nextInt();
            for(int j=0;j<2;j++) {
                a[i][j] = in.nextInt();
            }
        }
        in.close();
        for(int i=0;i<n;i++) {
            if(q[i]==1) {
                union_vertices(a[i][0]-1,a[i][1]-1,parent,rank);
            }
            else if(q[i]==2) {
                int z1 = find_root(a[i][0]-1,parent);
                int z2 = find_root(a[i][1]-1,parent);
                if(z1==z2) {
                        System.out.println("Y");
                }
                else
                        System.out.println("N");
            }
        }
    }

    public void initialise(int parent[],int rank[]) {
        for(int i=0;i<m;i++) {
            parent[i] = i;
        }
        for(int i=0;i<m;i++) {
            rank[i] = 0;
        }
    }

    public int find_root(int x1,int parent[]) {
        int x_root = x1;
        while(parent[x_root]!=x_root) {
            parent[x_root] = parent[parent[x_root]];
            x_root = parent[x_root];
        }
        return x_root;
    }

    public int union_vertices(int x2,int y,int parent[],int rank[]) {
        int x_root = find_root(x2,parent);
        int y_root = find_root(y,parent);
        if(x_root==y_root) {
            return 0;
        }
        else {
            if(rank[x_root]>rank[y_root]) {
                parent[y_root] = x_root;
            }
            else if(rank[x_root]<rank[y_root]) {
                parent[x_root] = y_root;
            }
            else {
                parent[x_root] = y_root;
                rank[y_root]++;
            }
            return 1;
        }
    }

}

by xxb123 @ 2021-01-26 22:15:08

就是2,9,10MLE,有大佬会减小内存嘛?救救孩子吧


by q779 @ 2021-01-26 22:55:11

建议换语言


by KarL05 @ 2021-01-28 08:21:57

@xxb123 你写复杂了 用个简单实现吧


by xxb123 @ 2021-01-28 13:11:46

@KarL05 我感觉我的代码逻辑和一些题解的逻辑是一样的,不知道你说的复杂是那个点呢?


by KarL05 @ 2021-01-28 14:19:19

简单的东西写复杂了, 常数上去了


by KarL05 @ 2021-01-28 14:19:35

@xxb123


|