1804E - Routing - CodeForces Solution

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 30;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, m;
vector< int > graph[maxn];
bool good[treesiz];
int dp[maxn][treesiz];
int ans[maxn];

int f(int x, int mask, int mini) {
	int &ret = dp[x][mask];
	if (ret != -1) return ret;

	ret = -2;
	for (int tren : graph[x]) {
		if (tren < mini) continue;
		if (tren == mini) {
			if (good[mask]) ret = mini;
		}
		if (mask & (1 << tren)) continue;
		if (f(tren, mask | (1 << tren), mini) != -2) ret = tren;
	}
	return ret;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b); a--, b--;

		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	int lim = (1 << n);
	for (int mask = 0; mask < lim; mask++) {
		bool flag = true;
		for (int i = 0; i < n; i++) {
			if (mask & (1 << i)) continue;
			bool tflag = false;
			for (int tren : graph[i]) {
				if (mask & (1 << tren)) tflag = true;
			}
			if (!tflag) flag = false;
		}
		good[mask] = flag;
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < lim; j++) dp[i][j] = -1;

	int sol = -2;
	for (int i = 0; i < n; i++) {
		if (f(i, 1 << i, i) != -2) sol = i;
	}

	if (sol == -2) printf("No\n");
	else {
		printf("Yes\n");
		int stat = sol;

		int cp = stat;
		int mask = 1 << sol;
		//printf("debug: %d\n", sol.X);
		while (true) {
			//printf("tren: %d %d\n", stat, mask);
			ans[stat] = dp[stat][mask];
			int nex = dp[stat][mask];
			if (nex == cp) break;
			//system("pause");

			stat = nex;
			mask |= (1 << nex);
		}

		for (int i = 0; i < n; i++) {
			if (mask & (1 << i)) continue;
			for (int tren : graph[i]) {
				if (mask & (1 << tren)) ans[i] = tren;
			}
		}

		for (int i = 0; i < n; i++) printf("%d ", ans[i] + 1);
		printf("\n");
	}
	return 0;
}