UVa : 10004 :: Bicoloring

Problem : Please find the problem here.

Explanation : The problem asks to check if the given graph is bipartite or not.

Code : Can be solved in O(N+M). Used DFS Algorithm.

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

const int mxN = 2e2;
int n, m, c[mxN];
vector<int> adj[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;
}

void init(){

    memset(c, -1, sizeof(c));
    for(int i = 0; i < n; i++){
        adj[i].clear();
    }
}

int main()
{

    while(scanf("%d %d", &n, &m) && n){

        init();
	for(int i = 0, u, v; i < m; i++){
	    cin >> u >> v;
	    adj[u].emplace_back(v);
	    adj[v].emplace_back(u);
	}

        bool ok = 1;
	for(int i = 0; i < n; i++){
	    if(c[i] < 0){
	        ok &= isBipartite(i);
	    }
	}
	cout << (!ok?"NOT BICOLORABLE.":"BICOLORABLE.") << '\n';
    }	
    return 0;
}

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;
}

SPOJ : Bugs Life Solution

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

const int mxN = 2e5;
vector<int> adj[mxN];
int n, m, c[mxN];

bool isBipartite(int u){
	bool res = 1;
	for(int v : adj[u]){
		if(c[v] != 0){
			if(c[v] == c[u]){
				return false;
			}
		}
		else{
			c[v] = -c[u];
			res &= isBipartite(v);
		}
	}
	return res;
}

int main()
{
	int t;
	cin >> t;
	for(int k = 1; k <= t; k++){
		cin >> n >> m;
		for(int i = 0; i < n; i++){
			c[i] = 0;
			adj[i].clear();
		}
		for(int i = 0, a, b; i < m; i++){
			cin >> a >> b, a--, b--;
			adj[a].emplace_back(b);
			adj[b].emplace_back(a);
		}
		
		bool ok = 1;
		for(int i = 0; i < n; i++){
			if(c[i] == 0){
				c[i] = 1;
				ok &= isBipartite(i);
			}
		}
		cout << "Scenario #" << k << ":\n";
		if(ok){
			cout << "No suspicious bugs found!";
		}else{
			cout << "Suspicious bugs found!";
		}
		cout << '\n';
	}
	return 0;
}