图论大杂烩
题目满足补图是二分图。
原图最大团$=$补图最大独立集$=|V|-$补图最大匹配。
加入边后,最大团变大 -> 删除补图的边后,补图的最大独立集变大 -> 删除补图的边后,补图的最大匹配变小。
于是原问题转化成了补图的最大匹配的必选边,对二分图建立流网络求最大流,问题转化为最大流(最小割)的必选边。
在残量网络上的未满流边跑$tarjan$,弧满流且两端点分别属于源点汇点所在$scc$,即为必选边。
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 20010, M = 400010, INF = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
int stk[N], top;
bool ins[N];
int id[N], scc_cnt;
int low[N], dfn[N], ts;
vector<pair<int, int>> ans;
int u[M], v[M];
int c[N];
void insert(int u, int v) {
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
void insert(int u, int v, int d) {
e[idx] = v, ne[idx] = h[u], f[idx] = d, h[u] = idx++;
e[idx] = u, ne[idx] = h[v], f[idx] = 0, h[v] = idx++;
}
bool bfs() {
int hh = 0, tt = -1;
memset(d, -1, sizeof d);
q[++tt] = S, d[S] = 0, cur[S] = h[S];
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (d[j] == -1 && f[i]) {
d[j] = d[t] + 1;
cur[j] = h[j];
if (j == T) return true;
q[++tt] = j;
}
}
}
return false;
}
void tarjan(int u) {
dfn[u] = low[u] = ++ts;
stk[++top] = u, ins[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
if (!f[i]) continue;
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (ins[j]) low[u] = min(low[u], dfn[j]);
}
if (low[u] == dfn[u]) {
scc_cnt++;
int y;
do {
y = stk[top--];
ins[y] = false;
id[y] = scc_cnt;
} while (y != u);
}
}
int find(int u, int limit) {
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
cur[u] = i;
int j = e[i];
if (d[j] == d[u] + 1 && f[i]) {
int t = find(j, min(f[i], limit - flow));
if (!t) d[j] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic() {
int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}
bool dfs(int u, int col) {
c[u] = col;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (c[j] == col) return false;
if (!c[j]) {
if (!dfs(j, -col)) return false;
}
}
return true;
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m;
S = 0, T = n + 1;
for (int i = 1; i <= m; i++) {
cin >> u[i] >> v[i];
insert(u[i], v[i]);
insert(v[i], u[i]);
}
for (int i = 1; i <= n; i++)
if (!c[i]) dfs(i, 1);
memset(h, -1, sizeof h), idx = 0;
for (int i = 1; i <= m; i++) {
if (c[u[i]] == 1) insert(u[i], v[i], 1);
else insert(v[i], u[i], 1);
}
for (int i = 1; i <= n; i++) {
if (c[i] == 1) insert(S, i, 1);
else insert(i, T, 1);
}
dinic();
for (int i = S; i <= T; i++)
if (!dfn[i]) tarjan(i);
for (int i = 0; i < 2 * m; i += 2) {
int from = e[i ^ 1], to = e[i];
if (from > to) swap(from, to);
if (!f[i] && id[from] != id[to]) ans.emplace_back(from, to);
}
sort(ans.begin(), ans.end());
cout << ans.size() << '\n';
for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
return 0;
}
tql! jls