EdgeColoring.cpp

#include <random>
#include "../utilities/template.h"

vi edgeColoring(int N, vector<pii> eds) {
	vi cc(N + 1), ret(sz(eds));
	for (pii e : eds) ++cc[e.first], ++cc[e.second];
	int u, v, ncols = *max_element(all(cc)) + 1;
	vector<vi> adj(N, vi(ncols, -1));
	vi fan(N), free(N), loc;
	for (pii e : eds) {
		tie(u, v) = e;
		fan[0] = v;
		loc.assign(ncols, 0);
		int at = u, end = u, d, c = free[u], cyc = 0, i = 0;
		while (d = free[v], !loc[d] && (v = adj[u][d]) != -1)
			loc[d] = ++cyc, cc[cyc] = d, fan[cyc] = v;
		cc[loc[d]] = c;
		for (int cd = d; at != -1; cd ^= c ^ d, at = adj[at][cd])
			swap(adj[at][cd], adj[end = at][cd ^ c ^ d]);
		for (; adj[fan[i]][d] != -1; i++) {
			int left = fan[i], right = fan[i + 1], e = cc[i + 1];
			adj[u][e] = left;
			adj[left][e] = u;
			adj[right][e] = -1;
			free[right] = e;
		}
		adj[u][d] = fan[i];
		adj[fan[i]][d] = u;
		for (int y : {fan[0], u, end})
			for (int& z = free[y] = 0; adj[y][z] != -1; z++);
	}
	rep(i,0,sz(eds))
		for (tie(u, v) = eds[i]; adj[u][ret[i]] != v;) ++ret[i];
	return ret;
}

int main() {
	std::mt19937 rng(2);
	int cnt = 0;
	rep(n,0,7) {
		cerr << endl << n << endl;
		rep(edbits,0,(1 << (n*(n-1)/2))) {
			vector<pii> ed;
			vi deg(n);
			int it = 0;
			rep(i,0,n) rep(j,i+1,n) {
				if (edbits & 1 << (it++)) {
					ed.push_back({i, j});
					deg[i]++;
					deg[j]++;
				}
			}
			int maxdeg = n == 0 ? 0 : *max_element(all(deg));
			auto test = [&]() {
				++cnt;
				if (cnt % 100 == 0) cerr << "\r" << cnt << flush;
				vi cols = edgeColoring(n, ed);
				assert(sz(cols) == sz(ed));
				vi usedCols(n);
				rep(i,0,sz(cols)) {
					assert(cols[i] <= maxdeg);
					int bc = 1 << cols[i];
					for (int x : {ed[i].first, ed[i].second}) {
						assert(!(usedCols[x] & bc));
						usedCols[x] |= bc;
					}
				}
			};
			if (n + sz(ed) <= 10) {
				// k! 2^k
				sort(all(ed));
				if (n != 0) do {
					rep(bi,0,(1 << sz(ed))) {
						if (bi) {
							int ind = __builtin_ctz(bi);
							swap(ed[ind].first, ed[ind].second);
						}
						test();
					}
				} while (next_permutation(all(ed)));
			} else {
				rep(it,0,10) {
					shuffle(all(ed), rng);
					for (auto& e : ed) if (rng() & 128) swap(e.first, e.second);
					test();
				}
			}
		}
	}
	cout << "Tests passed!" << endl;
	return 0;
}