题解 | 复合共轭图构造 线性做法

先 DFS 求图 2 连通块，然后 DFS 求图 1 连通块（碰到边连接图 2 两个不同连通块时删除这条边并且认为不连通），然后图 1 每多一个连通块就要多加一条边

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

int n;
int m1;
int m2;
vector<vector<int>> graph1;
vector<vector<int>> graph2;
vector<int> ltk;
int res;
vector<bool> vis;

void Dfs2(int x) {
    ltk[x] = res;
    for (const auto& y : graph2[x]) {
        if (!ltk[y]) {
            Dfs2(y);
        }
    }
}

void Dfs1(int x) {
    vis[x] = true;
    for (const auto& y : graph1[x]) {
        if (ltk[x] != ltk[y]) {
            res++;
            continue;
        }
        if (!vis[y]) {
            Dfs1(y);
        }
    }
}

void Solve() {
    cin >> n >> m1 >> m2;
    graph1.assign(n + 1, {});
    graph2.assign(n + 1, {});
    ltk.assign(n + 1, {});
    vis.assign(n + 1, false);
    while (m1--) {
        int u, v;
        cin >> u >> v;
        graph1[u].push_back(v);
        graph1[v].push_back(u);
    }
    while (m2--) {
        int u, v;
        cin >> u >> v;
        graph2[u].push_back(v);
        graph2[v].push_back(u);
    }
    res = 0;
    for (int i = 1; i <= n; i++) {
        if (!ltk[i]) {
            res++;
            Dfs2(i);
        }
    }
    res *= -2;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            res += 2;
            Dfs1(i);
        }
    }
    cout << res / 2 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        Solve();
    }
}
// 64 位输出请用 printf("%lld")