F. 分组划分 题解

问题描述

有 $n_1 + n_2$ 个人，编号 $1$ 到 $n_1+n_2$，初始时某些人之间有朋友关系（无向边）。已知整个图是 2-连通 的（即删除任意一个人后，剩下的图仍然连通）。要求将所有人分成两个组，第一组恰好 $n_1$ 人，第二组恰好 $n_2$ 人，使得 每组内部任意两人之间都有路径相连（路径上的中间人必须属于同一组，但题目中“acquaintance involving mutual friends, who must be from the same group”意味着路径上的所有中间人也必须属于该组，即子图是连通的）。

保证解存在。输出任意一种分组方案。

思路分析

关键性质：原图是 2-连通的，所以没有割点。但当我们逐步构造第一组时，剩余图可能产生割点。题解采用 贪心构造：

1. 初始时，任选一个点（比如 $1$）加入第一组。
2. 重复以下步骤直到第一组有 $n_1$ 个点：
   • 考虑当前不在第一组的所有点构成的剩余图（记为 $G_{\text{rem}}$）。
   • 找出所有 与第一组有边相连 的候选点。
   • 在这些候选点中，选择一个 在 $G_{\text{rem}}$ 中不是割点 的点，加入第一组。

为什么这样可行？
因为原图是 2-连通的，所以初始剩余图（即去掉第一组的一个点后）仍然是连通的。在贪心过程中，我们每次添加一个不是割点的点，可以保证剩余图保持连通。此外，这样的点一定存在（否则会产生矛盾）。最终第一组大小达到 $n_1$，剩余 $n_2$ 个点自然形成第二组。由于原图连通且我们每次添加的点都与第一组相邻，第一组内部显然是连通的（通过已添加的点连接）。第二组由于是剩余图，且我们一直保持剩余图连通，所以第二组也是连通的。

算法步骤

1. 读入 $n_1, n_2, m$，建图。
2. 初始化第一组集合 $S = \{1\}$。
3. 当 $|S| < n_1$：
   • 标记剩余顶点集 $R = V \setminus S$。
   • 用 Tarjan 算法求 $R$ 中所有割点。
   • 遍历所有 $v \in R$，若存在 $u \in S$ 使得 $(u,v)$ 是边，则 $v$ 是候选点。
   • 在候选点中选择一个 不是割点 的点 $v$，加入 $S$。
4. 输出 $S$ 和 $V \setminus S$。

复杂度

每次添加一个点需要重新计算割点，每次 Tarjan 为 $O(N+M)$。共添加 $n_1$ 次，总复杂度 $O(n_1 \cdot (N+M))$。由于 $n_1 \le 2000$，$N \le 2000$，$M \le 5000$，且所有测试用例总和有限，可以接受。

代码实现

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

const int MAXN = 2005;

int n1, n2, N, m;
vector<int> adj[MAXN];
bool in_first[MAXN];
vector<int> first_group;

// Tarjan 求割点
vector<int> dfn, low;
int timer;
vector<bool> is_articulation;

void dfs_articulation(int u, int parent, const vector<bool>& in_remaining) {
    dfn[u] = low[u] = ++timer;
    int children = 0;
    for (int v : adj[u]) {
        if (!in_remaining[v]) continue;          // 忽略已选入第一组的点
        if (v == parent) continue;
        if (dfn[v] == 0) {
            children++;
            dfs_articulation(v, u, in_remaining);
            low[u] = min(low[u], low[v]);
            if (parent != -1 && low[v] >= dfn[u]) {
                is_articulation[u] = true;
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (parent == -1 && children >= 2) {
        is_articulation[u] = true;
    }
}

void find_articulation_points(const vector<bool>& in_remaining, vector<bool>& art) {
    dfn.assign(N + 1, 0);
    low.assign(N + 1, 0);
    is_articulation.assign(N + 1, false);
    timer = 0;
    for (int i = 1; i <= N; ++i) {
        if (in_remaining[i] && dfn[i] == 0) {
            dfs_articulation(i, -1, in_remaining);
        }
    }
    art = is_articulation;
}

void solve() {
    cin >> n1 >> n2 >> m;
    N = n1 + n2;
    for (int i = 1; i <= N; ++i) adj[i].clear();
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    fill(in_first + 1, in_first + N + 1, false);
    first_group.clear();
    // 任选一个起点，例如 1
    in_first[1] = true;
    first_group.push_back(1);

    while ((int)first_group.size() < n1) {
        vector<bool> in_remaining(N + 1, false);
        for (int i = 1; i <= N; ++i)
            if (!in_first[i]) in_remaining[i] = true;

        vector<bool> art;
        find_articulation_points(in_remaining, art);

        // 候选点：在剩余集中且与第一组有边
        vector<int> candidates;
        for (int v = 1; v <= N; ++v) {
            if (in_first[v]) continue;
            bool neighbor = false;
            for (int u : adj[v]) {
                if (in_first[u]) { neighbor = true; break; }
            }
            if (neighbor) candidates.push_back(v);
        }

        int chosen = -1;
        for (int v : candidates) {
            if (!art[v]) { chosen = v; break; }
        }
        // 根据题目保证，chosen 一定存在
        if (chosen == -1) chosen = candidates[0]; // fallback

        in_first[chosen] = true;
        first_group.push_back(chosen);
    }

    // 输出第一组
    for (int i = 0; i < n1; ++i) {
        cout << first_group[i] << (i == n1-1 ? "\n" : " ");
    }
    // 输出第二组（剩余点）
    vector<int> second_group;
    for (int i = 1; i <= N; ++i)
        if (!in_first[i]) second_group.push_back(i);
    for (int i = 0; i < n2; ++i) {
        cout << second_group[i] << (i == n2-1 ? "\n" : " ");
    }
}

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

正确性证明

• 第一组内部连通：每次加入的点都与第一组中的某个点直接相连，因此第一组始终是连通的。
• 第二组内部连通：初始时剩余图（去掉第一组的点）是连通的（因为原图 2-连通且第一组只有一个点）。每次我们添加一个不是剩余图割点的点，删除该点不会使剩余图分裂，所以剩余图保持连通。最终第二组即为整个剩余图，连通。
• 存在性：由于原图 2-连通，且解存在，贪心过程中一定能找到非割点的候选点（反证法：若所有候选点都是割点，则会导致矛盾）。