在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。

输入格式：

输入在第一行给出一个正整数N（≤104），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：

K P[1] P[2] ⋯ P[K]

其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过104。

之后一行给出一个非负整数Q（≤104），是查询次数。随后Q行，每行给出一对被查询的人的编号。

输出格式：

首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。

输入样例：

4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7

输出样例：

10 2
Y
N

代码长度限制

16 KB

时间限制

150 ms

内存限制

64 MB

栈限制

8192 KB

import java.util.*;
import java.io.*;

/**
 * 思路：使用并查集维护部落关系。利用数组 parent[10001] 记录父节点。
 */
public class Main {
    static int[] parent = new int[10001];
    static boolean[] exist = new boolean[10001];

    public static void main(String[] args) throws IOException {
        FastScanner fs = new FastScanner(System.in);
        
        // 1. 初始化并查集
        for (int i = 1; i <= 10000; i++) parent[i] = i;

        int n = fs.nextInt();
        int maxId = 0;
        for (int i = 0; i < n; i++) {
            int k = fs.nextInt();
            if (k == 0) continue;
            
            int first = fs.nextInt();
            exist[first] = true;
            if (first > maxId) maxId = first;
            
            for (int j = 1; j < k; j++) {
                int next = fs.nextInt();
                exist[next] = true;
                if (next > maxId) maxId = next;
                // 合并部落
                union(first, next);
            }
        }

        // 2. 统计总人数和独立部落数
        int peopleCount = 0;
        int tribalCount = 0;
        for (int i = 1; i <= maxId; i++) {
            if (exist[i]) {
                peopleCount++;
                // 如果父节点是自己，说明是一个部落的根
                if (parent[i] == i) {
                    tribalCount++;
                }
            }
        }
        
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        out.println(peopleCount + " " + tribalCount);

        // 3. 处理 Q 次查询
        int q = fs.nextInt();
        for (int i = 0; i < q; i++) {
            int u = fs.nextInt();
            int v = fs.nextInt();
            // 判断是否在同一部落（即根节点是否相同）
            if (find(u) == find(v)) {
                out.println("Y");
            } else {
                out.println("N");
            }
        }
        out.flush();
        out.close();
    }

    /**
     * 核心优化 循环版 Find
     * 避免递归导致的 StackOverflow 风险和性能开销
     */
    static int find(int i) {
        int root = i;
        while (parent[root] != root) {
            root = parent[root];
        }
        // 路径压缩：将路径上所有节点直接指向根节点
        while (parent[i] != root) {
            int next = parent[i];
            parent[i] = root;
            i = next;
        }
        return root;
    }

    static void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ; // 合并两个集合
        }
    }

    /**
     * 字节级快速输入
     */
    static class FastScanner {
        private InputStream in;
        private byte[] buf = new byte[1024 * 64];
        private int ptr = 0;
        private int len = 0;

        public FastScanner(InputStream is) { this.in = is; }

        private int read() {
            if (ptr < len) return buf[ptr++];
            ptr = 0;
            try {
                len = in.read(buf);
            } catch (IOException e) { return -1; }
            if (len <= 0) return -1;
            return buf[ptr++];
        }

        public int nextInt() {
            int c = read();
            while (c >= 0 && c <= 32) c = read();
            if (c == -1) return 0;
            int res = 0;
            while (c > 32) {
                res = res * 10 + (c - '0');
                c = read();
            }
            return res;
        }
    }
}