 # CNNCT2 - Editorial

Author: Alexey Zayakin
Tester: Hanlin Ren
Editorialist: Hanlin Ren

HARD

# PREREQUISITES:

Matroid Intersection

# 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.

# 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];

vector<int> getNonBridges();
} G1, G2;

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);

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;
}

7 Likes

Can’t this problem be solved without the knowledge of matroids ? Can a participant solve this without the knowledge of matroids… As I think very few people might know about matroids.

1 Like

very deep topic…doesn’t even hear this name… 4 Likes

I’m not quite sure I understand the alternate explanation completely. The matroid intersection will give us the largest independent set, that forms a forest in both graphs. But how do we extend that to ensure both graphs are connected with minimum number of edges.

And I don’t understand why this answer is

2 Likes

We first choose the m edges in the largest independent set, so each graph has n-m connected components now. Then we choose n-m-1 edges in each graph to connect both graphs. We need m+2(n-m-1)=2n-2-m edges.

I see! Thanks @r_64! That makes it a lot clearer. Just one question though. How are we sure that picking n-m-1 edges in each graph is optimal?

By that I mean, why is it not possible that some of these n-m-1 edges could connect components in both graphs thus allowing us to pick some number of edges < 2*(n-m-1) (since some edges could be common).

Thanks again!

Because m is the maximum.

Suppose we pick M\le 2n-2 edges so that both graphs are connected. For each graph we only preserve an (arbitrary) spanning tree of these M edges, then these two spanning trees has at most m edges in common (since m is the maximum). Then M\ge 2n-m-2.