题目链接

复合共轭图构造

题目描述

给定两个拥有 个顶点的无向图 和 。我们可以对图 执行任意次操作：添加一条边或移除一条边。目标是求使得图 和图 的连通性完全相同的最小操作次数。

“连通性完全相同”指的是：对于任意两个顶点 和 ，当且仅当它们在图 中连通（存在路径）时，它们在图 中也连通。

解题思路

  1. 分析题目条件

    题目的核心要求是修改图 ，使其连通分量划分与图 的完全一致。例如，如果顶点 在图 中构成一个连通分量， 构成另一个，那么在修改后的图 中， 和 也必须是对应的连通分量。

  2. 分类处理 F 的边

    我们可以根据图 的连通性，将图 的所有边分为两类：

    • “坏边”: 如果一条边 连接的两个顶点在图 中不连通，那么这条边在最终的图 中绝对不能存在，因为它会错误地连接两个本应分离的连通分量。所有这样的“坏边”都必须被移除。
    • “好边”: 如果一条边 连接的两个顶点在图 中是连通的，那么这条边有助于维持 中所需的连通性，可以保留。

  3. 计算操作次数

    • 移除次数: 我们首先用并查集计算出图 的所有连通分量。然后遍历图 的每一条边 ，如果 和 属于 的不同连通分量，就记为一条“坏边”。需要移除的边的数量就等于“坏边”的数量。
    • 添加次数: 移除所有“坏边”后，图 只剩下“好边”，形成了一个新的图 。现在， 的每个连通分量都完全包含在 的某个连通分量之内（即 的连通分量划分是 的一个“细分”）。我们的任务是通过添加最少的边，将 的连通分量合并，使其与 的连通分量完全一致。
      • 假设图 有 个连通分量。
      • 假设图 有 个连通分量。
      • 为了将 个分量合并成 个目标分量，我们需要的最小边数是 。
    • 总操作数 = (移除“坏边”的数量) + ()

  4. 算法实现

    1. 使用并查集 uf_g 计算图 的连通分量。
    2. 初始化另一个并查集 uf_f_good。
    3. 遍历图 的所有边 ：
      • 如果 在 uf_g 中不连通，则该边为“坏边”，移除次数加一。
      • 如果 在 uf_g 中连通，则该边为“好边”，在 uf_f_good 中合并 。
    4. 统计 uf_g 和 uf_f_good 中的连通分量数量 和 。
    5. 计算总操作数为 坏边数 + k_f_good - k_g。

代码

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

struct DSU {
    vector<int> parent;
    int components;
    DSU(int n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
        components = n;
    }

    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
            components--;
        }
    }
};

void solve() {
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    vector<pair<int, int>> edges_f(m1);
    for (int i = 0; i < m1; ++i) {
        cin >> edges_f[i].first >> edges_f[i].second;
    }
    
    DSU uf_g(n);
    for (int i = 0; i < m2; ++i) {
        int u, v;
        cin >> u >> v;
        uf_g.unite(u, v);
    }

    DSU uf_f_good(n);
    int removals = 0;
    for (const auto& edge : edges_f) {
        if (uf_g.find(edge.first) != uf_g.find(edge.second)) {
            removals++;
        } else {
            uf_f_good.unite(edge.first, edge.second);
        }
    }

    int additions = uf_f_good.components - uf_g.components;
    cout << removals + additions << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.stream.IntStream;

class DSU {
    private int[] parent;
    public int components;

    public DSU(int n) {
        parent = new int[n + 1];
        IntStream.rangeClosed(0, n).forEach(i -> parent[i] = i);
        components = n;
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    public void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
            components--;
        }
    }
}

public class Main {
    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        int m1 = sc.nextInt();
        int m2 = sc.nextInt();

        int[][] edgesF = new int[m1][2];
        for (int i = 0; i < m1; i++) {
            edgesF[i][0] = sc.nextInt();
            edgesF[i][1] = sc.nextInt();
        }
        
        DSU ufG = new DSU(n);
        for (int i = 0; i < m2; i++) {
            ufG.unite(sc.nextInt(), sc.nextInt());
        }

        DSU ufFGood = new DSU(n);
        int removals = 0;
        for (int[] edge : edgesF) {
            if (ufG.find(edge[0]) != ufG.find(edge[1])) {
                removals++;
            } else {
                ufFGood.unite(edge[0], edge[1]);
            }
        }
        
        int additions = ufFGood.components - ufG.components;
        System.out.println(removals + additions);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
}

import sys

# It's recommended to increase recursion limit for deep DSU paths in Python
sys.setrecursionlimit(200005)

class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.components = n

    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            self.parent[root_i] = root_j
            self.components -= 1
            return True
        return False

def solve():
    line = sys.stdin.readline()
    if not line: return
    n, m1, m2 = map(int, line.split())
    
    edges_f = []
    for _ in range(m1):
        edges_f.append(list(map(int, sys.stdin.readline().split())))
        
    uf_g = DSU(n)
    for _ in range(m2):
        u, v = map(int, sys.stdin.readline().split())
        uf_g.unite(u, v)
        
    uf_f_good = DSU(n)
    removals = 0
    for u, v in edges_f:
        if uf_g.find(u) != uf_g.find(v):
            removals += 1
        else:
            uf_f_good.unite(u, v)
    
    additions = uf_f_good.components - uf_g.components
    print(removals + additions)

def main():
    t_str = sys.stdin.readline()
    if not t_str: return
    t = int(t_str)
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：并查集 (Disjoint Set Union)
  • 时间复杂度：。我们需要处理图 和图 的所有边，每次并查集操作的平均时间复杂度接近常数，为 （反阿克曼函数）。
  • 空间复杂度：。需要 空间存储两个并查集数组，以及 空间存储图 的边。