UVa : 11396 :: Claw Decomposition

Problem : Please find the problem here.

Summary : For each claw, the centre node can be colored blue while three corner nodes can be colored with red. So we just need to check if this condition always holds i.e if the vertices of the graph can colored with just two colors i.e Bipartite check!

Code: Used DFS.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 3e2;
int n, m, c[mxN], u, v;
vector<int> adj[mxN];
bool vis[mxN];

bool isBipartite(int u, int cu=0){
	if(c[u] != -1){
		if(cu^c[u]){
			return false;
		}
		return true;
	}
	c[u] = cu;
	bool ok = 1;
	for(int v : adj[u]){
		ok &= isBipartite(v, cu^1);
	}
	return ok;
}
int main()
{
	ofstream fout("out");
	while(scanf("%d", &n) && n){
		for(int i = 0; i < n; i++){
			adj[i].clear();
		}
		while(scanf("%d %d", &u, &v) && (u && v)){
			u--, v--;
			adj[u].emplace_back(v);
			adj[v].emplace_back(u);
		}
		
		bool ok = 1;
		memset(c, -1, sizeof(c));
		for(int i = 0; i < n; i++){
			if(c[i] < 0){
				ok &= isBipartite(i);
			}
		}
		cout << (ok?"YES":"NO") << '\n';
	}
	return 0;
}