Bài toán yêu cầu xác định xem hai người có cùng một tổ tiên (thuộc cùng một nhóm họ hàng) hay không, dựa trên các mối quan hệ đã cho. Đây là bài toán kinh điển áp dụng cấu trúc dữ liệu Union-Find (Disjoint Set Union - DSU).

Dưới đây là cách triển khai bằng Java:

import java.util.Scanner;

public class Main {
    static int[] parent;

    // Khởi tạo mỗi phần tử là cha của chính nó
    static void makeSet(int n) {
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

    // Tìm gốc với nén đường đi
    static int findRoot(int x) {
        if (parent[x] != x) {
            parent[x] = findRoot(parent[x]);
        }
        return parent[x];
    }

    // Gộp hai tập hợp chứa x và y
    static void unionSets(int x, int y) {
        int rootX = findRoot(x);
        int rootY = findRoot(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // Số người
        int m = sc.nextInt(); // Số mối quan hệ
        int q = sc.nextInt(); // Số truy vấn

        makeSet(n);

        // Xử lý các mối quan hệ
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            unionSets(u, v);
        }

        // Trả lời các truy vấn
        for (int i = 0; i < q; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            System.out.println(findRoot(u) == findRoot(v) ? "Yes" : "No");
        }
    }
}

Một ứng dụng tương tự là bài LeetCode 547: Number of Provinces, trong đó ma trận kề biểu diễn kết nối giữa các thành phố, và cần đếm số lượng nhóm liên thông (tỉnh).

public class Solution {
    static int[] dsu;

    static void init(int n) {
        dsu = new int[n];
        for (int i = 0; i < n; i++) {
            dsu[i] = i;
        }
    }

    static int find(int x) {
        if (dsu[x] != x) {
            dsu[x] = find(dsu[x]);
        }
        return dsu[x];
    }

    static void merge(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra != rb) dsu[ra] = rb;
    }

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        init(n);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    merge(i, j);
                }
            }
        }

        int provinces = 0;
        for (int i = 0; i < n; i++) {
            if (dsu[i] == i) provinces++;
        }
        return provinces;
    }
}