题目链接：https://codeforces.com/contest/1916/problem/F
题意
已知点双连通的图 \(G = (V, E)\)。求一种划分方式 \(V = V_1 \cup V_2\)，使得 \(|V_1| = n_1\)，\(|V_2| = n_2\)，且 \(G\) 的两生成子图 \(G[V_1]\)，\(G[V_2]\) 均连通。
\(n_1, n_2 \le 2000\)，\(m \le 5000\)。
题解（官解）
首先给出构造方式：初始化 \(|V_1|\) 为任意只包含一个点的集合，之后向其中一次加入一个满足下面条件的 \(|V_2|\) 中的点 \(v\)：
-
\(v\) 在原图中与 \(G[V_1]\)连通；
-
\(v\) 不是 \(G[V_2]\) 的割点。
显然这样的构造方式一定符合要求。下面证明这样的点一定存在：
-
若 \(G[V_2]\) 中没有割点，则显然一定存在。
-
否则，选取 \(G[V_2]\) 的一个割点 \(u\)，使得 \(G[V_2 - u]\) 至少有一个连通片 \(W\) 中没有 \(G[V_2]\) 的割点（这样的点一定存在，可以从 Tarjan 算法的 dfs 树考虑）。则 \(W\) 中必然有点与 \(V_1\) 相邻，否则删去 \(u\) 后 \(W\) 与 \(V_1\) 在原图中不连通，与原图点双连通的条件矛盾。取这样的点作为答案即可。
时间复杂度 \(O(n_1(n_1 + n_2 + m))\)。
代码实现
void solve() {
int n1, n2, m;
cin >> n1 >> n2 >> m;
int n = n1 + n2;
vector<pair<int, int>> es(m);
vector<vector<int>> oadj(n);
for (int ei = 0; ei < m; ei++) {
int u, v;
cin >> u >> v;
u--, v--;
oadj[u].push_back(v);
oadj[v].push_back(u);
es[ei] = {u, v};
}
vector<bool> choose(n, false);
choose[0] = true;
for (int _ = 1; _ < n1; _++) {
int nxt = -1;
vector<vector<int>> adj(n);
for (auto [u, v] : es) {
if (!choose[u] && !choose[v]) {
adj[u].push_back(v);
adj[v].push_back(u);
}
}
auto cut = cut_vertices(adj);
for (int i = 0; i < n; i++) {
if (choose[i]) {
for (int j : oadj[i]) {
if (!choose[j] && !cut[j]) nxt = j;
}
}
}
assert(nxt != -1);
choose[nxt] = true;
}
for (int i = 0; i < n; i++)
if (choose[i]) cout << i + 1 << " ";
cout << "\n";
for (int i = 0; i < n; i++)
if (!choose[i]) cout << i + 1 << " ";
cout << "\n";
}