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