CNNCT2 - Editorial

PROBLEM LINK:

Div 1
Div 2
Practice

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

DIFFICULTY:

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.

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;
}
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…:frowning:

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.