PROBLEM LINK:
Author: Alexey Zayakin
Tester: Hanlin Ren
Editorialist: Hanlin Ren
DIFFICULTY:
HARD
PREREQUISITES:
PROBLEM:
Given integers N,M and two undirected graphs with N nodes and M edges, find the smallest subset of \{1,2,\dots,M\} such that, if we only consider edges whose index is in this subset, then both graphs are connected.
QUICK EXPLANATION:
For every graph G, the set of edges E'\subseteq E such that G-E' is connected forms a matroid. Therefore we can use matroid intersection algorithm to solve this problem.
EXPLANATION:
Please see here for a very detailed explanation of matroid intersection algorithm.
In this editorial we prove that the problem is really a matroid intersection problem. Given a graph G=(V,E), a subset of edges E'\subseteq E is an independent set if after removing E' from G, the graph G is still connected. (The terminology āindependent setā follows matroid theory; donāt confuse it with the āindependent setā in graph theory!)
Weāll prove that the independent sets indeed form a matroid. Then, we find the largest common independent set E' of two graphs, and delete them. The rest edges are the edges that we should open.
There are three axioms of matroids: (copied from Wikipedia)
The empty set is independent. This is obvious to see.
Hereditary Property. That is, every subset of independent set is also independent. This is also obvious: you canāt disconnect a graph by removing less edges (i.e. add edges).
Augmentation Property. If A and B are two independent sets, and |A|>|B|, then there is an edge e\in A\setminus B such that B\cup\{e\} is also an independent set.
Imagine we perform three operations on the graph:
- First we remove all edges in A. By definition of independent sets, the graph is still connected.
- Then we remove all edges in B\setminus A. Itās easy to see that the remaining graph has at most |B\setminus A|+1 connected components.
- Then we add the edges in A\setminus B back. Since A\cup (B\setminus A)=A\cup B, now the graph becomes the original graph with edges in B removed. Thus the graph becomes connected now.
Let x=|A\setminus B| and y=|B\setminus A|. Since |A|>|B|, we have x>y. In the last step, we added x edges to a graph with at most y+1 components, and the graph becomes connected (i.e. has only 1 component). Since x>y, there must be some edge e\in A\setminus B that, when added into the graph, the number of connected components doesnāt change. (You can also refer to Kruskalās algorithm to think about this process.) If you then remove e from the current graph (i.e. remove B\cup\{e\} from the original graph), the graph should still be connected.
ALTERNATE EXPLANATION:
There is another formulation of the problem into a matroid intersection problem. For each graph we consider its graphic matroid. That is, a set of edges forms an independent set if they form a forest. We find the largest common independent set, say it has size m, and the number of edges we should open is 2n-2-m.
BTW, please feel free to share your approaches!
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int MX = 300;
int n, m;
bool enabled[MX];
struct graph_t {
int u[MX], v[MX];
void read();
vector<int> getNonBridges();
} G1, G2;
void graph_t::read() {
for (int i = 0; i < m; i++) {
ignore = scanf("%d %d", u + i, v + i);
u[i]--;
v[i]--;
}
}
vector<int> graph_t::getNonBridges() {
static vector<pair<int, int>> G[MX];
for (int i = 0; i < n; i++) G[i].clear();
for (int i = 0; i < m; i++) {
if (enabled[i] == false) continue;
G[u[i]].emplace_back(v[i], i);
G[v[i]].emplace_back(u[i], i);
}
static bool vis[MX];
static int up[MX], dep[MX];
fill(vis, vis + n, false);
vector<int> result;
function<void(int, int, int)> dfs = [&](int v, int p, int d) {
vis[v] = true;
dep[v] = d;
up[v] = d;
for (auto& e : G[v]) {
if (e.second == p) continue;
if (vis[e.first] == false) {
dfs(e.first, e.second, d + 1);
if (up[e.first] <= d) result.push_back(e.second);
}
else {
if (dep[e.first] < d) result.push_back(e.second);
}
up[v] = min(up[v], up[e.first]);
}
};
dfs(0, -1, 0);
return result;
}
namespace ExchangeGraph {
vector<int> G[MX];
void clear() {
for (int i = 0; i < m; i++) G[i].clear();
}
void addEdge(int u, int v) {
G[u].push_back(v);
}
bool findAugmentalPath(vector<int> from, vector<int> to) {
vector<int> par(m, -1), dist(m), queue;
for (int v : from) {
queue.push_back(v);
par[v] = -2;
dist[v] = 0;
}
for (size_t i = 0; i < queue.size(); i++) {
int v = queue[i];
for (int u : G[v]) {
if (par[u] == -1) {
queue.push_back(u);
par[u] = v;
dist[u] = dist[v] + 1;
}
}
}
int target = -1;
for (int v : to) {
if (par[v] == -1) continue;
if (target == -1 || dist[v] < dist[target]) target = v;
}
if (target != -1) {
while (target != -2) {
enabled[target] = not enabled[target];
target = par[target];
}
return true;
}
return false;
}
}
int main() {
int T;
ignore = scanf("%d", &T);
while (T--) {
ignore = scanf("%d %d", &n, &m);
G1.read();
G2.read();
fill(enabled, enabled + m, true);
int ans = m;
while (true) {
ExchangeGraph::clear();
auto Y1 = G1.getNonBridges();
auto Y2 = G2.getNonBridges();
if (ExchangeGraph::findAugmentalPath(Y1, Y2)) {
ans--;
continue;
}
for (int e = 0; e < m; e++) {
if (enabled[e]) continue;
enabled[e] = true;
auto edgesTo = G1.getNonBridges();
auto edgesFrom = G2.getNonBridges();
enabled[e] = false;
for (int v : edgesTo) ExchangeGraph::addEdge(e, v);
for (int v : edgesFrom) ExchangeGraph::addEdge(v, e);
}
if (ExchangeGraph::findAugmentalPath(Y1, Y2)) {
ans--;
}
else {
break;
}
}
printf("%d\n", ans);
}
return 0;
}
