package LeetCode;

public class LC_1971 {
    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {0, 2}, {3, 5}, {5, 4}, {4, 3}};
        System.out.println(validPath(6, edges, 3, 2));
    }

    public static boolean validPath(int n, int[][] edges, int source, int destination) {
        int[] fa = new int[n];
        init(fa);
        for (int i = 0; i < edges.length; i++) {
            join(fa, edges[i][0], edges[i][1]);
        }
        return isSame(fa, source, destination);
    }

    public static void init(int[] fa) {
        for (int i = 0; i < fa.length; i++) {
            fa[i] = i;
        }
    }

    public static void join(int[] fa, int u, int v) {
        u = find(fa, u);
        v = find(fa, v);
        if (u == v) return;
        fa[v] = u;
    }

    public static int find(int[] fa, int x) {
        if (x == fa[x]) return x;
        else {
            fa[x] = find(fa, fa[x]);
            return fa[x];
        }
    }

    public static boolean isSame(int[] fa, int u, int v) {
        u = find(fa, u);
        v = find(fa, v);
        return u == v;
    }
}