Contest Duration: ~ (local time) (90 minutes) Back to Home

Submission #5359923

Source Code Expand

Copy
```import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {

public static void main(String[] args) {
FastScanner sc = new FastScanner();

int n = sc.nextInt();
int q = sc.nextInt();

int[] p = new int[q];
int[] a = new int[q];
int[] b = new int[q];

for(int i=0;i<q;i++){
p[i] = sc.nextInt();
a[i] = sc.nextInt();
b[i] = sc.nextInt();
}

UnionFindTree uf = new UnionFindTree(n);

for(int i=0;i<q;i++){

if(p[i]==0){
uf.unite(a[i], b[i]);
}
else{
if(uf.isEquivalent(a[i], b[i])){
System.out.println("Yes");
}
else{
System.out.println("No");
}
}

}

}

}

class UnionFindTree {
int[] par;
int[] rank;
int[] peers; //仲間の数

public UnionFindTree(int n){
par = new int[n];
rank = new int[n];
peers = new int[n];

for(int i=0;i<n;i++){
par[i] = i;
peers[i] = 1;
}
}

//木の根を求める
int find(int x){
if(par[x] == x){
return x;
}
else{
return par[x] = find(par[x]);
}
}

//xとyの属する集合を併合
void unite(int x, int y){
int px = find(x);
int py = find(y);

if(px == py){
return;
}
else if(rank[px] < rank[py]){
peers[py] += peers[px];
par[px] = py;

}
else{
peers[px] += peers[py];
par[py] = px;
if(rank[px]==rank[py]){
rank[px]++;
}
}

}

//xとyが同じ集合に属するか
boolean isEquivalent(int x, int y){
return find(x) == find(y);
}

//xの仲間の数を求める
int peersnum(int x){
return peers[find(x)];
}
}

class FastScanner {
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}else{
ptr = 0;
try {
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
while(isPrintableChar(b)) {
sb.appendCodePoint(b);
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
if (b == '-') {
minus = true;
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while(true){
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
}else if(b == -1 || !isPrintableChar(b)){
return minus ? -n : n;
}else{
throw new NumberFormatException();
}
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() { return Double.parseDouble(next());}
}```

#### Submission Info

Submission Time 2019-05-11 22:23:10+0900 B - Union Find warachia Java8 (OpenJDK 1.8.0) 100 3940 Byte AC 1285 ms 71516 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_sample_01.txt
Case Name Status Exec Time Memory
00_sample_01.txt 71 ms 20436 KB