2022/round3/first_time_ch1.cpp

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

int N, M, K;
vector<unordered_map<int, int>> C;  // C[b][p] = bin b stakes with DSU parent p
unordered_set<int> S;               // Set of currently uniform bin numbers

void update_parent(int i, int r_old, int r_new) {
  if (r_old == r_new) {
    return;
  }
  auto &bin = C[i / K];
  if (--bin[r_old] == 0) {
    bin.erase(r_old);
  }
  bin[r_new]++;
  if (bin.size() == 1) {
    S.insert(i / K);
  } else {
    S.erase(i / K);
  }
}

struct disjoint_sets {
  vector<vector<int>> values;
  vector<int> parent, color_of_parent, parent_of_color;

 public:
  disjoint_sets(int N)
      : values(N), parent(N), color_of_parent(N), parent_of_color(N) {
    for (int i = 0; i < N; i++) {
      values[i] = {i};
      parent[i] = i;
      color_of_parent[i] = i;
      parent_of_color[i] = i;
    }
  }

  // O(M + N log N) across M calls to unite().
  void unite(int a, int b) {
    a = parent[a];
    b = parent[b];
    if (a != b) {
      if (values[a].size() < values[b].size()) {
        swap(a, b);
      }
      while (!values[b].empty()) {
        int v = values[b].back();
        values[b].pop_back();
        update_parent(v, parent[v], a);
        parent[v] = a;
        color_of_parent[v] = color_of_parent[a];
        values[a].push_back(v);
      }
    }
  }

  void repaint(int c1, int c2) {
    int pa = parent_of_color[c1];
    if (pa == -1) {
      return;
    }
    color_of_parent[pa] = c2;
    parent_of_color[c1] = -1;
    int pb = parent_of_color[c2];
    if (pb == -1) {
      parent_of_color[c2] = pa;
      return;
    }
    unite(pa, pb);
    color_of_parent[pb] = c2;
    parent_of_color[c2] = parent[pb];
  }
};

int solve() {
  cin >> N >> M >> K;
  int nbins = (N + K - 1) / K;  // ceil(N / K)
  // Initialize parent counts.
  C.assign(nbins, {});
  for (int i = 0; i < N; i++) {
    C[i / K][i]++;
  }
  S.clear();
  for (int b = 0; b < nbins; b++) {
    if (C[b].size() == 1) {
      S.insert(b);
    }
  }
  int ans = (S.size() == nbins ? 0 : -1);
  disjoint_sets DS(N);
  for (int i = 0, a, b; i < M; i++) {
    cin >> a >> b;
    DS.repaint(--a, --b);
    if (S.size() == nbins && ans < 0) {
      ans = i + 1;
    }
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}