Map Colouring

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

vector<int> g[17];
int am[17][17];

int u[17];

int f=0;

void dfs(int x, int c){
	if (f) return;
	if (u[x]>2) return;
	if (u[x]==0){
		u[x]=c;
	}
	else{
		if (u[x]!=c){
			f=1;
		}
		return;
	}
	for (int nx:g[x]){
		dfs(nx, 3-c);
	}
}

int isbp(int n){
	f=0;
	for (int i=1;i<=n;i++){
		if (u[i]==0){
			dfs(i, 1);
			if (f) return 0;
		}
	}
	return 1;
}

void solve(){
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++) g[i].clear();
	for (int i=1;i<=n;i++){
		for (int ii=1;ii<=n;ii++) am[i][ii]=0;
	}
	for (int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		a++;
		b++;
		g[a].push_back(b);
		g[b].push_back(a);
		am[a][b]=1;
		am[b][a]=1;
	}
	if (m==0){
		cout<<1<<'\n';
		return;
	}
	for (int i=1;i<=n;i++) u[i]=0;
	if (isbp(n)){
		cout<<2<<'\n';
		return;
	}
	for (int b=1;b<(1<<n);b++){
		for (int i=0;i<n;i++){
			if (b&(1<<i)){
				u[i+1]=3;
			}
			else{
				u[i+1]=0;
			}
		}
		int ff=0;
		for (int i=1;i<=n;i++){
			if (u[i]==0) continue;
			for (int ii=i+1;ii<=n;ii++){
				if (u[i]==u[ii]&&am[i][ii]){
					ff=1;
					break;
				}
			}
		}
		if (ff) continue;
		if (isbp(n)){
			cout<<"3\n";
			return;
		}
	}
	for (int b=1;b<(1<<n);b++){
		for (int i=0;i<n;i++){
			if (b&(1<<i)){
				u[i+1]=3;
			}
			else{
				u[i+1]=0;
			}
		}
		if (!isbp(n)) continue;
		for (int i=0;i<n;i++){
			if (b&(1<<i)){
				u[i+1]=0;
			}
			else{
				u[i+1]=3;
			}
		}
		if (!isbp(n)) continue;
		cout<<"4\n";
		return;
	}
	cout<<"many"<<endl;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tcs;
	cin>>tcs;
	for (int tc=0;tc<tcs;tc++){
		solve();
	}
}

Test 1

Verdict: ACCEPTED