graphDestruction.md

E - Graph Destruction

Approach

• concept of reverse DSU
• we will do the reverse of Destruction that is creation, because it's what DSU allow us to do.
• During creation we will make all edges concerning that vertex, except those who yet not revived which are smaller vertices then the current one.
• we will increment the count as proceed and decrease the count as we unite.

DSU snippets

Code

  int n, m;
  cin >> n >> m;

  std ::vector<std ::vector<int>> graph(n + 1);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  dsu.init(n + 10);
  std ::vector<int> ans{0};
  int count = 0;

  for (int u = n; u >= 2; u--) {
    count++;
    for (const auto &v : graph[u]) {
      if (v < u)
        continue;
      if (!dsu.isSameSet(u, v)) {
        dsu.unionSet(v, u);
        count--;
      }
    }
    ans.push_back(count);
  }

  reverse((ans).begin(), (ans).end());
  for (const auto &i : ans)
    cout << i << '\n';