CSES :: Graph Algorithms :: Round Trip

Problem : Please find the problem here.

Explanation : We need to find out the path in the graph where start and end node is the same (a cycle).
This can be easily checked with simple Graph Traveral, check if any of the node's children node, during traversal, is already visited by some other parent.

Code : Used DFS to check cycles in the graph and backtracking the path using the nodes parent array maintained over traversal.

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e5;

void DFS(int u, int pu, vector<int> (&adj)[mxN], vector<int> &visited, vector<int> &parent) {
    visited[u] = 1;
    parent[u] = pu;

    for (int v : adj[u]) {
        if (!visited[v]) {
            DFS(v, u, adj, visited, parent);
        } else {
            if (v == pu) {
                continue;
            }
            else {
                int u2 = u;
                vector<int> ans;
                while (u^v) {
                    ans.emplace_back(u);
                    u = parent[u];
                }

                ans.push_back(v);
                ans.push_back(u2);

                cout << ans.size() << '\n';
                for (auto a : ans) {
                    cout << a+1 << ' ';
                }
                exit(0);
            }

        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> adj[mxN], visited(n, 0), parent(n, 0);


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

    for (int i = 0; i < n; i++) {
        if (!visited[i]) DFS(i, -1, adj, visited, parent);
    }

    cout << "IMPOSSIBLE";

    return 0;
}

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

Uva : 11080 :: Place the Guards

Problem : Please find the problem here.
Summary : Here if the given graph is not bipartite there cannot be any guards placed in any junction, so the answer in this case is just -1. On the other hand if the graph is Bipartite we have to output minimum number of junctions that connects all the other junctions (for all the connected components).
Code: Used dfs to traverse all the connected components and returned if the graph is Bipartite or not. Also counted the minimum number of vertices(juntions) which connects all the other vertices.

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

const int mxN = 200;
int n, m, c[mxN], r, b;
vector<int> adj[mxN];

bool isBipartite(int u, int cu = 0){
    if(c[u] != -1){
        if(cu^c[u]){
            return false;
        }
        return true;
    }
    bool ok = 1;
    c[u] = cu;
    if(cu == 0){
        r++;
    }
    else if(cu == 1){
        b++;
    } 
    for(int v : adj[u]){
        ok &= isBipartite(v, cu^1);
    }
    return ok;
}

int main()
{
    ofstream fout("out");
    int t;
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i = 0; i < n; i++){
            adj[i].clear();
        }
        for(int i = 0, a, b; i < m; i++){
            cin >> a >> b;
            adj[a].emplace_back(b);
            adj[b].emplace_back(a);
        }
        memset(c, -1, sizeof(c));
        bool ok = true;
        int cnt = 0;
        r = 0, b = 0;
        for(int i = 0; i < n; i++){
            if(c[i] < 0){
                r = 0, b = 0;
                ok &= isBipartite(i);
                cnt += max(1, min(r, b));
            }
        }
        if(!ok){
            cout << -1 << '\n';
        }else{
            cout << cnt << '\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;
}