AcWing1251 打击罪犯--并查集

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int) (x).size()
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> VI;
typedef double db;

const int N = 1010;
int n, p[N], sz[N];
VI a[N];
int find(int x) {
  if (p[x] != x) p[x] = find(p[x]);
  return p[x];
}
void solve() { 
  cin >> n;
  for (int i = 0; i < N; i++) {
    p[i] = i;
    sz[i] = 1;
  }
  for (int i = 1; i <= n; i++) {
    int m, x;
    cin >> m;
    while (m--) {
      cin >> x;
      a[i].pb(x);
    }
  }
  for (int i = n; i >= 1; i--) { // 从后往前找k
    int pi = find(i);
    for (auto &x: a[i]) { // 所有有联系的点
      int px = find(x);
      if (x > i) { // 如果x < i，那么x在警察干掉i之前已经寄了，所以不需要加入集合
        if (px != pi) {
          p[px] = pi;
          sz[pi] += sz[px];
        }
      }
    }
    if (sz[pi] > n/2) { // 如果大于n/2，那你小子就是最后一个
      cout << i << '\n';
      return;
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}