Submission #1515248

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
 
public class UnionFind {
    private int[] _par;
    private int[] _rank;
 
    public UnionFind(int size) {
        _par = new int[size+1];
        _rank = new int[size+1];
 
        for (int i = 0; i < _par.Length; i++) {
            _par[i] = i;
        }
    }
 
    int Root(int x) {
        if (_par[x] == x)
            return x;
        else {
            _par[x] = Root(_par[x]);
            return _par[x];
        }
    }
 
    public bool IsSame(int x, int y) {
        return Root(x) == Root(y);
    }
 
    public void Unite(int x, int y) {
        x = Root(x);
        y = Root(y);
        if (x == y) return;
 
        if (_rank[x] < _rank[y]) {
            _par[x] = y;
        }
        else {
            _par[y] = x;
            if (_rank[x] == _rank[y]) {
                _rank[x]++;
            }
        }
    }
}
 
class Program {
    static int ReadInt() {
        return int.Parse(Console.ReadLine());
    }
 
    static int[] ReadInts() {
        return Console.ReadLine().Trim().Split().Select(int.Parse).ToArray();
    }
 
    static string ReadLine() {
        return Console.ReadLine().Trim();
    }
 
    static string[] ReadStrings() {
        return Console.ReadLine().Trim().Split();
    }
 
    static void Main() {
        var nq = ReadInts();
        int n = nq[0], q = nq[1];
 
        var uni = new UnionFind(n);
        for (int i = 0; i < q; i++) {
            var pab = ReadInts();
            int p = pab[0], a = pab[1], b = pab[2];
 
            if (p == 0) { // union
                uni.Unite(a, b);
            }
            else { // query
                Console.WriteLine(uni.IsSame(a, b) ? "Yes" : "No");
            }
        }
    }
}

Submission Info

Judge Result