[PAT-A] 1118 Birds in Forest

Java

测试点3、4超时

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

public class Main {
    static final int N = 10010;
    static int[] p = new int[N];
    static int[] birds = new int[N];
    static Set<Integer> st = new HashSet<>();

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

    static void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa != pb) {
            if (pa > pb) {
                int temp = pa;
                pa = pb;
                pb = temp;
            }
            p[pb] = pa;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(System.out);

        for (int i = 1; i < N; ++i) {
            p[i] = i;
        }

        int n = Integer.parseInt(reader.readLine());
        for (int i = 0; i < n; ++i) {
            String[] parts = reader.readLine().split(" ");
            int k = Integer.parseInt(parts[0]);
            for (int j = 0; j < k; ++j) {
                birds[j] = Integer.parseInt(parts[j + 1]);
                st.add(birds[j]);
            }

            for (int j = 0; j < k - 1; ++j) {
                union(birds[j], birds[j + 1]);
            }
        }

        int cnt = 0;
        for (int i : st) {
            if (find(i) == i) {
                cnt++;
            }
        }
        writer.printf("%d %d\n", cnt, st.size());

        int Q = Integer.parseInt(reader.readLine());
        for (int i = 0; i < Q; ++i) {
            String[] query = reader.readLine().split(" ");
            int a = Integer.parseInt(query[0]);
            int b = Integer.parseInt(query[1]);
            if (find(a) == find(b)) {
                writer.println("Yes");
            } else {
                writer.println("No");
            }
        }

        writer.flush();
        writer.close();
        reader.close();
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 10010;

int n;
int p[N], bird[N];
unordered_set<int> st;

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

void Union(int a, int b) {
    if (a > b) swap(a, b);
    p[find(b)] = find(a);
}

int main() {
    for (int i = 1; i < N; ++i) p[i] = i;

    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int k;
        scanf("%d", &k);
        for (int j = 0; j < k; ++j) {
            scanf("%d", &bird[j]);
            st.insert(bird[j]);
        }

        for (int j = 0; j < k - 1; ++j)
            Union(bird[j], bird[j + 1]);
    }

    int cnt = 0;
    for (auto i: st)
        if (p[i] == i) cnt++;
    printf("%d %d\n", cnt, st.size());

    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (p[find(a)] == find(b)) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}