CareerCup

The problem can be viewed as a graph problem. "Given the graph, determine if the graph is bipartite". In other words, is it possible to color the graph using two colors such that no nodes with the same color are connected? Proposed solution assumes that the graph is connected:

(i) using the pairs, construct a graph G
(ii) chose any node as a source node
(iii) starting from the source node, perform BFS, at each step, color the neighbors, toggle the color. If a neighbor is already colored with different color, the graph is not bipartite, return None
(iv) group nodes by color and return two sets

class Bipartite:

    def __init__(self, G):
        self.G = G
        self.st = {}

    def test(self, src):
        if (self._is_bipartite(src)):   return self._split()
        else:                           return None

    def _is_bipartite(self, src):
        q = deque()
        q.append(src)           # enqueue source

        color = 0               # initial color label
        while not q.empty():
            curr = q.pop()
            if st.has_key(curr):
                continue        # skip node
            self.st[curr] = color

            for node in G.neighbours(curr):
                if not st.has_key(node):
                    q.append(node)
                else if self.st[node] == color:
                        return False
            color = color^1     # toggle color label

        return True

    def _split(self):
        A = set()
        B = set()
        for node in st.keys():
            if st[key]:     A.add(node)
            else:           B.add(node)
        return A,B

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class SplitRelations {
	static class Node{
		int val;
		Set<Node> set;
		int tag;
		Node(int val){
			this.val = val;
			set = new HashSet<Node>();
			tag = -1;
		}
	}

	static void ProcessRelationList(int[][] relationList, HashSet<Node> set0, HashSet<Node> set1) throws Exception{
		HashMap<Integer, Node> map  = new HashMap<Integer, Node>();

		for (int i=0; i< relationList.length; i++){
			int rel1 = relationList[i][0];
			int rel2 = relationList[i][1];
			if (!map.containsKey(rel1)){
				map.put(rel1, new Node(rel1));
			}
			if (!map.containsKey(rel2)){
				map.put(rel2, new Node(rel2));
			}
			Node node1 = map.get(rel1);
			Node node2 = map.get(rel2);
			node1.set.add(node2);
			node2.set.add(node1);
		}

		Integer[] keyArr = map.keySet().toArray(new Integer[map.size()]);
		Queue<Node> q = new LinkedList<Node>();
		q.add(map.get(keyArr[0]));
		map.get(keyArr[0]).tag = 0;

		while(!q.isEmpty()){
			Node node = q.remove();
			int childTag = (node.tag+1)%2;
			if (node.tag == 0){
				set0.add(node);
			}else if (node.tag == 1){
				set1.add(node);
			}
			for (Node child: node.set){
				child.set.remove(node);
				if (child.tag == -1){
					child.tag = childTag;
				}else if (child.tag!= childTag){
					throw new Exception("Parent " + node.val + "'s Child " + child.val + " is in " + child.tag + " Retrying in :" + childTag);
				}
				q.add(child);
			}
			node.set.clear();
		}
	}

	static void PrintSet(HashSet<Node> set1,HashSet<Node> set2){
		Node[] arr1 = set1.toArray(new Node[set1.size()]);
		Node[] arr2 = set2.toArray(new Node[set2.size()]);
		System.out.print("Set1 : ");
		for (int i=0; i< arr1.length; i++){
			System.out.print(arr1[i].val + ((i==arr1.length-1)?(""):(", ")));
		}
		System.out.print("   Set2 : ");
		for (int i=0; i< arr2.length; i++){
			System.out.print(arr2[i].val + ((i==arr2.length-1)?(""):(", ")));
		}
		System.out.println();
	}

	public static void main(String[] args){
		HashSet<Node> set1 = new HashSet<Node>();
		HashSet<Node> set2 = new HashSet<Node>();
		int[][] relationList;

		set1.clear();
		set2.clear();
		relationList = new int[][] {{1,2}, {2,3}, {3,4}};
		try {
			ProcessRelationList(relationList, set1, set2);
			PrintSet(set1, set2);
		} catch (Exception e) {
			System.out.println("Exception : " + e.getMessage());
		}

		set1.clear();
		set2.clear();
		relationList = new int[][] {{1,2}, {1,3}, {2,3}, {3,4}};
		try {
			ProcessRelationList(relationList, set1, set2);
			PrintSet(set1, set2);
		} catch (Exception e) {
			System.out.println("Exception : " + e.getMessage());
		}
	}
}

yeah it's a problem of bipartite graph :)

yeah it's a problem to check ,given graph is bipartite or not !!

bool split(vector<pair<int, int>> rel)
{
	map<int,node*> myset;

	for (auto r : rel)
	{
		if (myset.find(r.first) != myset.end())
		{
			node* t = myset[r.first];
			t->friends.push_back(r.second);
			if (myset.find(r.second) != myset.end())
			{
				t = myset[r.second];
				t->friends.push_back(r.first);
			}
			else
			{
				t = new node(r.second);
				myset[r.second] = t;
				t->friends.push_back(r.first);
			}
		}
		else
		{
			node* t = new node(r.first);
			t->friends.push_back(r.second);
			myset[r.first] = t;
			if (myset.find(r.second) != myset.end())
			{
				t = myset[r.second];
				t->friends.push_back(r.first);
			}
			else
			{
				t = new node(r.second);
				myset[r.second] = t;
				t->friends.push_back(r.first);
			}
		}
	}

	int color = 1;
	for (auto item : myset)
	{
		for (auto f : item.second->friends)
		{
			if (myset[f]->color == 0)
				myset[f]->color=color;
			else
				if (myset[f]->color != color)
					return false;
			myset[f]->color = color;
		}
		color = color == 1 ? 2 : 1;
	}
	return true;
}

Check whether the graph is bipartite. A simple solution using dfs. (1 and -1 are used for colors)

public static class Graph {
    int n;
    List<Integer>[] adjList;
    int[] colors;

    public Graph(int n) {
      this.n = n;
      adjList = (ArrayList<Integer>[])new ArrayList[n];
      colors = new int[n];
      for (int i=0; i<n; i++) {
        adjList[i] = new ArrayList<Integer>();
      }
    }

    public void addEdge(int u, int v) {
      adjList[u].add(v);
      adjList[v].add(u);
    }

    public boolean isGroupingPossible(int root, int color) {
      if (colors[root] == 0) colors[root] = color;
      else if (colors[root]!=color) {
        return false;
      } else {
        return true;
      }

      for (Integer child : adjList[root]) {
        if (!isGroupingPossible(child, color*-1)) return false;
      }
      return true;
    }

  }

package google;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class SplitUsersIntoGroups {
	public static void main(String args[]) {
		int[][] friendRelations = { { 1, 2 }, { 2, 3 }, { 3, 4 } };

		HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();

		for (int i = 0; i < friendRelations.length; i++) {

			checkAndPut(friendRelations[i][0], friendRelations[i][1], map);
			checkAndPut(friendRelations[i][1], friendRelations[i][0], map);
		}

		HashSet<Integer> visited = new HashSet<Integer>();

		boolean result = true;
		for (int cur : map.keySet()) {

			if (!visited.contains(cur)) {
				HashSet<Integer> group1 = new HashSet<Integer>();
				HashSet<Integer> group2 = new HashSet<Integer>();
				boolean curGrp1 = true;
				result = result && recurseFindGroupable(group1, group2, curGrp1, cur, map);
				visited.addAll(group1);
				visited.addAll(group2);
			}

		}

		System.out.println(result);

	}

	private static boolean recurseFindGroupable(HashSet<Integer> group1, HashSet<Integer> group2, boolean curGrp1,
			int cur, HashMap<Integer, ArrayList<Integer>> map) {
		HashSet<Integer> curSet = curGrp1 ? group1 : group2;
		HashSet<Integer> otherSet = curGrp1 ? group2 : group1;
		boolean result = true;
		if (curSet.contains(cur)) {
			return true;
		} else if (otherSet.contains(cur)) {
			return false;
		} else {
			curSet.add(cur);
		}
		for (int user : map.get(cur)) {
			result = result && recurseFindGroupable(group1, group2, !curGrp1, user, map);
		}
		return result;
	}

	public static void checkAndPut(int first, int second, HashMap<Integer, ArrayList<Integer>> map) {
		if (map.containsKey(first)) {
			map.get(first).add(second);
		} else {
			ArrayList<Integer> list = new ArrayList<Integer>();
			list.add(second);
			map.put(first, list);
		}
	}
}

#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

class Node
{
    public:
        vector<Node*> to_nodes_;
};

bool IsConnectedComponentBipartite(Node* start_node, unordered_set<Node*>& seen)
{
    unordered_map<Node*, bool> part;
    queue<Node*> q;
    q.push(start_node);
    part[start_node] = true;
    while (!q.empty())
    {
        Node* n = q.front();
        q.pop();
        if (seen.find(n) == seen.end())
        {
            seen.insert(n);
            bool p = part[n];
            for (Node* to_node : n->to_nodes_)
            {
                auto it = part.find(to_node);
                if (it != part.end())
                {
                    if (it->second != !p)
                    {
                        return false;
                    }
                }
                else
                {
                    part[to_node] = !p;
                }
                q.push(to_node);
            }
        }
    }
    return true;
}

bool IsBipartite(const vector<Node*>& nodes)
{
    unordered_set<Node*> seen;
    for (Node* n : nodes)
    {
        if (seen.find(n) == seen.end())
        {
            if (!IsConnectedComponentBipartite(n, seen))
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    Node n1, n2, n3, n4;
    vector<Node*> graph = {&n1, &n2, &n3, &n4};

    n1.to_nodes_.push_back(&n2);
    n2.to_nodes_.push_back(&n1);

    n2.to_nodes_.push_back(&n3);
    n3.to_nodes_.push_back(&n2);

    n3.to_nodes_.push_back(&n4);
    n4.to_nodes_.push_back(&n3);

    cout << IsBipartite(graph) << "\n";

    n3.to_nodes_.push_back(&n1);
    n1.to_nodes_.push_back(&n3);

    cout << IsBipartite(graph) << "\n";

    return 0;
}