DFSMatching

Simple bipartite matching algorithm. Graph g should be a list of neighbors of the left partition, and btoa should be a vector full of -1's of the same size as the right partition. Returns the size of the matching. btoa[i] will be the match for vertex i on the right side, or -1 if it's not matched.

Time: O(VE) 22 lines works

Usage: vi btoa(m, -1); dfsMatching(g, btoa);

content/graph/DFSMatching.h — Lukas Polacek

bool find(int j, vector<vi>& g, vi& btoa, vi& vis) {
	if (btoa[j] == -1) return 1;
	vis[j] = 1; int di = btoa[j];
	for (int e : g[di])
		if (!vis[e] && find(e, g, btoa, vis)) {
			btoa[e] = di;
			return 1;
		}
	return 0;
}
int dfsMatching(vector<vi>& g, vi& btoa) {
	vi vis;
	rep(i,0,sz(g)) {
		vis.assign(sz(btoa), 0);
		for (int j : g[i])
			if (find(j, g, btoa, vis)) {
				btoa[j] = i;
				break;
			}
	}
	return sz(btoa) - (int)count(all(btoa), -1);
}