并查集算法

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;
const int N = 1E4 + 10;

int n, k, q, u, v;
int max_bird_id; // input中最大鸟的编号

vector<int> p(N);

int Find(int x) {
  return p[x] ^ x ? p[x] = Find(p[x]) : x;
}

bool isConnected(int u, int v) {
  return Find(u) == Find(v);
}

int count; // count 为合并了多少条边
void Union(int u, int v) {
  const int pu = Find(u);
  const int pv = Find(v);
  if (pu == pv) return;
  p[pu] = pv;

  ++count;
}

int main(void) {
  // Initialize UnionFind Data Structure
  iota(begin(p), end(p), 0);

  cin >> n;
  while (n--) {
    cin >> k;
    vector<int> birds(k);
    for (int i = 0; i < k; ++i) { 
      cin >> birds[i];
      if (birds[i] > max_bird_id) max_bird_id = birds[i];
    }
    for (int i = 0; i < k - 1; ++i)
      Union(birds[i], birds[i + 1]);
  }

  printf("%d %d\n", max_bird_id - count, max_bird_id);
  cin >> q;
  while (q--) {
    cin >> u >> v;
    puts(isConnected(u, v) ? "Yes" : "No");
  }
}