java 并查集已路径优化还T？

Bonnie123456 @ 2019-11-27 16:37:36

by KellyFrog @ 2019-11-27 17:04:39

@Bonnie123456 对的，java显然比cpp慢，是语言劣势

by yuanye15978 @ 2020-01-05 11:52:42

太坑爹啦

by yuanye15978 @ 2020-01-05 12:10:06

优化输入输出之后过了 Scanner速度慢、耗内存 System.out没缓存，速度比较慢

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author Administrator
 */

public class Main {

    static int N;
    static int M;

    static short[] nodes;

    static Random random = new Random(System.currentTimeMillis());

    private static void connectRoot(short i, short j) {
        if (random.nextInt(2) == 0) {
            nodes[i] = j;
        } else {
            nodes[j] = i;
        }

    }

    private static void connect(short i, short j) {
        short iroot = root(i);
        short jroot = root(j);
        connectRoot(iroot, jroot);
    }

    private static short root(short i) {
        if (nodes[i] == i) {
            return i;
        } else {
            nodes[i] = root(nodes[i]);
            return nodes[i];
        }
    }

    private static boolean connected(short i, short j) {
        return root(i) == root(j);
    }

    private static BufferedOutputStream out = new BufferedOutputStream(System.out, 16 * 1024);
    private static PrintWriter writer = (new PrintWriter(out));

    private static void run(int type, short x, short y) {
        if (type == 1) {
            connect(x, y);
        } else {
            if (connected(x, y)) {
                writer.append("Y\n");
            } else {
                writer.append("N\n");
            }
        }
    }

    private static void init() {
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = (short) i;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        nodes = new short[N];
        init();
        for (int i = 0; i < M; i++) {
            int type = scanner.nextInt();
            short x = (short) (scanner.nextShort() - 1);
            short y = (short) (scanner.nextShort() - 1);
           run(type, x, y);
        }
        writer.flush();
    }
}
class Scanner {
    private BufferedInputStream in;

    int c;

    boolean atBeginningOfLine;

    public Scanner(InputStream stream) {
        in = new BufferedInputStream(stream, 4 * 1024);
        try {
            atBeginningOfLine = true;
            c = (char) in.read();
        } catch (IOException e) {
            c = -1;
        }
    }

    public boolean hasNext() {
        if (!atBeginningOfLine) {
            throw new Error("hasNext only works " +
                    "after a call to nextLine");
        }
        return c != -1;
    }

    public String next() {
        StringBuffer sb = new StringBuffer();
        atBeginningOfLine = false;
        try {
            while (c <= ' ') {
                c = in.read();
            }
            while (c > ' ') {
                sb.append((char) c);
                c = in.read();
            }
        } catch (IOException e) {
            c = -1;
            return "";
        }
        return sb.toString();
    }

    public String nextLine() {
        StringBuffer sb = new StringBuffer();
        atBeginningOfLine = true;
        try {
            while (c != '\n') {
                sb.append((char) c);
                c = in.read();
            }
            c = in.read();
        } catch (IOException e) {
            c = -1;
            return "";
        }
        return sb.toString();
    }

    public int nextInt() {
        String s = next();
        try {
            return Integer.parseInt(s);
        } catch (NumberFormatException e) {
            return 0;
        }
    }

    public int nextShort() {
        String s = next();
        try {
            return Short.parseShort(s);
        } catch (NumberFormatException e) {
            return 0;
        }
    }

    public double nextDouble() {
        return new Double(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public void useLocale(int l) {
    }
}