ははは

質問リンク

白俊#1717。しゅうごうひょうげん

解答方法

ユニオンフィールド練習問題です!これはわかりませんが、問題で実現する演算は、集合のマージか同じ集合か->ルートを検索し、要素を重ならないdisjointの性質を持つため、union findの使用を容易に決定できます.
これは単純なUnion Find実装の問題であるが、find演算とunion演算の実装については、以下のように説明する.

find演算の実装
まずターゲットは集合(ツリー)のルートを見つけることです.ルートを表す-1の値が使用されます.また,伸ばされた構造では時間的に不利であり,ルートを検索する単純な演算しか必要ないので,ルートが見つかったら,その要素をルートの下に直接掛ける!

コンビネーション演算の実装
2つの要素が同じコレクションに属しているかどうかを確認します.(ルート比較を求める)異なる集合に属する場合は、ある要素が属する集合を別の要素の下に掛けます!easy!

コード#コード#

import java.util.Scanner;

public class RepresentingSet {
    static final int ROOT = -1;
    static int[] p;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

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

        p = new int[n + 1];
        for (int i = 0; i <= n; i++) p[i] = ROOT;

        StringBuilder result = new StringBuilder();
        while( m-- > 0) {
            int op = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();

            if (op == 0) {
                merge(a, b);
            } else {
                if (find(a) == find(b)) result.append("YES\n");
                else result.append("NO\n");
            }
        }

        System.out.print(result.toString());
    }

    private static int find(int n) {
        if (p[n] == ROOT) return n;
        else {
            p[n] = find(p[n]);
            return p[n];
        }
    }

    private static void merge(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);

        if (aRoot != bRoot) p[bRoot] = a;
    }
}

🤓🤓