並查集（Union-Find）は集合の結合と検索を効率的に行うデータ構造である。基本操作は結合（Union）と検索（Find）で、経路圧縮を適用することで平均計算量をO(α(n))に低下させる。結合時のランクを考慮した最適化（ランク統合）も有効である。

削除操作を扱う際は、逆順処理が有効である。初期状態で全ての削除を適用した後の連結成分数を計算し、逆順に各削除を復元しながら連結成分数を更新する。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 1000000;

int parent[MAX_N + 1];
int size[MAX_N + 1];
bool is_removed[MAX_N + 1];
vector<int> adj[MAX_N + 1];

int find_root(int x) {
    if (parent[x] == x) return x;
    parent[x] = find_root(parent[x]);
    return parent[x];
}

void union_sets(int a, int b) {
    a = find_root(a);
    b = find_root(b);
    if (a == b) return;
    if (size[a] < size[b]) swap(a, b);
    parent[b] = a;
    if (size[a] == size[b]) size[a]++;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m;
    vector<pair<int, int>> edge_list;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edge_list.push_back({u, v});
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        int node;
        cin >> node;
        is_removed[node] = true;
    }
    int connected_components = n - k;
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    for (auto &edge : edge_list) {
        int u = edge.first, v = edge.second;
        if (is_removed[u] || is_removed[v]) continue;
        if (find_root(u) != find_root(v)) {
            union_sets(u, v);
            connected_components--;
        }
    }
    vector<int> results;
    results.push_back(connected_components);
    for (int i = k - 1; i >= 0; i--) {
        int node = i + 1; // 逆順処理用
        is_removed[node] = false;
        connected_components++;
        for (int neighbor : adj[node]) {
            if (is_removed[neighbor]) continue;
            if (find_root(node) != find_root(neighbor)) {
                union_sets(node, neighbor);
                connected_components--;
            }
        }
        results.push_back(connected_components);
    }
    for (int i = results.size() - 1; i >= 0; i--) {
        cout << results[i] << '\n';
    }
    return 0;
}

敵対関係の管理には拡張ドメインを用いる。各ノードを複数のドメインに分割し、関係をドメイン間の結合で表現する。

敵の敵は友の関係を扱う際は、2ドメインモデルを用いる。ノードiを友人ドメイン（i）と敵人ドメイン（i + n）に分割し、敵対関係をドメイン間の結合で表現する。

#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 100000;

int root[MAX_N * 2 + 1];
int rank[MAX_N * 2 + 1];

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

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (rank[a] < rank[b]) swap(a, b);
    root[b] = a;
    if (rank[a] == rank[b]) rank[a]++;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= 2 * n; i++) {
        root[i] = i;
        rank[i] = 1;
    }
    int groups = n;
    for (int i = 0; i < m; i++) {
        char relation;
        int a, b;
        cin >> relation >> a >> b;
        if (relation == 'F') {
            if (find(a) != find(b)) {
                merge(a, b);
                groups--;
            }
        } else {
            if (find(a) == find(b + n) || find(b) == find(a + n)) {
                // 逆関係が既存
            } else {
                merge(a, b + n);
                merge(b, a + n);
            }
        }
    }
    cout << groups << endl;
    return 0;
}

食物連鎖問題（NOI2001）では3ドメインモデルを用いる。ノードiをi（A群）, i + n（B群）, i + 2n（C群）に分割し、A→B→C→Aの関係を維持する。

#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 100000;

int parent[MAX_N * 3 + 1];
int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= 3 * n; i++) {
        parent[i] = i;
    }
    int false_count = 0;
    for (int i = 0; i < k; i++) {
        int type, x, y;
        cin >> type >> x >> y;
        if (x > n || y > n) {
            false_count++;
            continue;
        }
        if (type == 1) {
            if (find(x) == find(y + n) || find(x + n) == find(y)) {
                false_count++;
            } else {
                parent[find(x)] = find(y);
                parent[find(x + n)] = find(y + n);
                parent[find(x + 2 * n)] = find(y + 2 * n);
            }
        } else {
            if (x == y) {
                false_count++;
            } else if (find(x) == find(y) || find(x) == find(y + n)) {
                false_count++;
            } else {
                parent[find(x)] = find(y + 2 * n);
                parent[find(x + n)] = find(y);
                parent[find(x + 2 * n)] = find(y + n);
            }
        }
    }
    cout << false_count << endl;
    return 0;
}