CareerCup

public class CheckIfAGraphIsBipartite {

	
	public static void main(String[] args) {
		List<Integer> allNodes = new ArrayList<>();
		UndirectedGraphNode n1 = new UndirectedGraphNode(1);
		UndirectedGraphNode n2 = new UndirectedGraphNode(2);
		UndirectedGraphNode n3 = new UndirectedGraphNode(3);
		UndirectedGraphNode n4 = new UndirectedGraphNode(4);
		UndirectedGraphNode n5 = new UndirectedGraphNode(5);
		UndirectedGraphNode n6 = new UndirectedGraphNode(6);
		UndirectedGraphNode n7 = new UndirectedGraphNode(7);
		UndirectedGraphNode n8 = new UndirectedGraphNode(8);
		UndirectedGraphNode n9 = new UndirectedGraphNode(9);
		UndirectedGraphNode n10 = new UndirectedGraphNode(10);
		
		n1.neighbors.add(n2);
		n1.neighbors.add(n3);
		n1.neighbors.add(n4);
		
		n2.neighbors.add(n1);
		n3.neighbors.add(n1);
		n4.neighbors.add(n1);
		
		n2.neighbors.add(n5);
		n3.neighbors.add(n5);
		
		n5.neighbors.add(n2);
		n5.neighbors.add(n3);
		
		n3.neighbors.add(n6);
		
		n6.neighbors.add(n3);
		n6.neighbors.add(n5);
		
		allNodes.add(n1.label);
		allNodes.add(n2.label);
		allNodes.add(n3.label);
		allNodes.add(n4.label);
		allNodes.add(n5.label);
		allNodes.add(n6.label);
		/*allNodes.add(n7.label);
		allNodes.add(n8.label);
		allNodes.add(n9.label);
		allNodes.add(n10.label);*/
		
		System.out.println(isBipartite(n1, allNodes));
	}
	
	public static boolean isBipartite(UndirectedGraphNode node, List<Integer> allNodes) {
		List<List<Integer>> nodes = new ArrayList<>();
		List<Integer> set1 = new ArrayList<>();
		List<Integer> set2 = new ArrayList<>();
		nodes.add(set1);nodes.add(set2);
		
		isBipartite(node, nodes, 0);
		
		if(allNodes.size() == (set1.size() + set2.size())){
			for (Integer integer : set2) {
				if(set1.contains(integer))
					return false;
			}
			for (Integer integer : set1) {
				if(set2.contains(integer))
					return false;
			}
		}else{
			return false;
		}
		return true;
	}
	
	public static List<List<Integer>> isBipartite(UndirectedGraphNode node, List<List<Integer>> nodes, int partition) {
		if(node == null) return nodes;
		if(node.visited) return nodes;
		
		List<UndirectedGraphNode> list = node.neighbors;
		if(partition == 0){
			partition = 1;
		}else{
			partition = 0;
		}
		nodes.get(partition).add(node.label);
		node.visited = true;
		for (UndirectedGraphNode undirectedGraphNode : list) {
			nodes = isBipartite(undirectedGraphNode, nodes, partition);
		}
		
		return nodes;
	}
}

class UndirectedGraphNode {
	int label;
	List<UndirectedGraphNode> neighbors;
	boolean visited;

	public UndirectedGraphNode(int x) {
		label = x;
		neighbors = new ArrayList<>();
	}
}

package google;

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

public class IsBipartite {
	public static class UndirectedGraphNode {
		int label;
		List<UndirectedGraphNode> neighbors;

		UndirectedGraphNode(int x) {
			label = x;
			neighbors = new ArrayList<UndirectedGraphNode>();
		}
	}

	public static class UndirectedGraph {
		protected HashMap<Integer, UndirectedGraphNode> nodes;

		public UndirectedGraph(UndirectedGraphNode... nodes) {
			this.nodes = new HashMap<Integer, UndirectedGraphNode>();
			for (UndirectedGraphNode node : nodes) {
				this.nodes.put(node.label,node);
			}
		}

		public UndirectedGraph() {
			this.nodes = new HashMap<Integer, UndirectedGraphNode>();
		}
		
		public boolean contains(int NodeID){
			return nodes.containsKey(NodeID);
		}
	}

	public static void main(String args[]) {
		UndirectedGraphNode n1 = new UndirectedGraphNode(1);
		UndirectedGraphNode n2 = new UndirectedGraphNode(2);
		UndirectedGraphNode n3 = new UndirectedGraphNode(3);
		UndirectedGraphNode n4 = new UndirectedGraphNode(4);
		UndirectedGraphNode n5 = new UndirectedGraphNode(5);
		UndirectedGraphNode n6 = new UndirectedGraphNode(6);
		

		n1.neighbors.add(n2);
		n1.neighbors.add(n3);
		n1.neighbors.add(n4);

		n2.neighbors.add(n1);
		n3.neighbors.add(n1);
		n4.neighbors.add(n1);

		n2.neighbors.add(n5);
		n3.neighbors.add(n5);

		n5.neighbors.add(n2);
		n5.neighbors.add(n3);

		n3.neighbors.add(n6);

		n6.neighbors.add(n3);

		UndirectedGraph undirectedGraph = new UndirectedGraph(n1, n2, n3, n4, n5, n6);

		System.out.println(isBipartite(undirectedGraph));

	}

	public static boolean isBipartite(UndirectedGraph undirectedGraph) {
		boolean result = true;
		HashSet<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
		for (int node : undirectedGraph.nodes.keySet()) {
			if (!visited.contains(undirectedGraph.nodes.get(node))) {
				HashSet<UndirectedGraphNode> set1 = new HashSet<UndirectedGraphNode>();
				HashSet<UndirectedGraphNode> set2 = new HashSet<UndirectedGraphNode>();
				HashSet<UndirectedGraphNode> curSet = set1;
				result = result && recurseFindBipartite(curSet, undirectedGraph.nodes.get(node), set1, set2);
				visited.addAll(set1);
				visited.addAll(set2);
			}
		}
		return result;

	}

	private static boolean recurseFindBipartite(HashSet<UndirectedGraphNode> curSet, UndirectedGraphNode curNode,
			HashSet<UndirectedGraphNode> set1, HashSet<UndirectedGraphNode> set2) {
		HashSet<UndirectedGraphNode> otherSet = (curSet == set1 ? set2 : set1);
		if (otherSet.contains(curNode)) {
			return false;
		}
		if (curSet.contains(curNode)) {
			return true;
		} else {
			curSet.add(curNode);
		}
		boolean result = true;
		for (UndirectedGraphNode neighbor : curNode.neighbors) {
			result = result && recurseFindBipartite(otherSet, neighbor, set1, set2);
		}
		return result;
	}
}

for a graph to be biparte each node in graph should have alternate labels.

traverse the graph in DFS, and keep on toggling the label of new nodes(nodes with label 0) and explore them further, if a node is already explored(label != 0) and has same label as its previous node then its not biparte.

public boolean isBipartite(List<UndirectedGraphNode> node)
{
	for(UnidirectedGraphNode n : node.neighbours)
	{
		if(n.label == 0)
		{
			n.label = 1+ (2 - node.label);
			if(!isBipartite(n))
				return false;
		}
		else if(n.label == node.label)
			return false;
	}
	
	return true;
}

C#:

public class Node
        {
            public int val;
            public List<Node> adjacent;

            public Node(int val)
            {
                this.val = val;
                this.adjacent = new List<Node>();
            }
        }

	public void IsBipartite()
            {
                List<int> set1 = new List<int>();
                List<int> set2 = new List<int>();

                Node source = graph.First().Value;

                if (IsBipartite(source, set1, set2, true))
                {
                    Console.WriteLine("Graph is Bipartite");
                }
                else
                {
                    Console.WriteLine("Graph is not Bipartite");
                }
            }	


	// Is Graph Bipartite
            // For a graph to be bipartite; itshould have two sets of distinct vertices whose;
            // Intersection is an empty set
            // Union consists of all vertices in the Graph

            // Create 2 Lists to represent this set
            // Set sourceIsSet2 to true for the first/root node of the graph
            public bool IsBipartite(Node current, List<int> set1, List<int> set2, bool sourceIsSet2)
            {
                // If the current node is already in set2 and source node was also in set2; 
                // return false else true
                if (set2.Contains(current.val))
                    return sourceIsSet2 ? false : true;

                // If the current node is already in set1 and source node was also in set2; 
                // return false else true
                else if (set1.Contains(current.val))
                    return sourceIsSet2 ? true : false;
                                
                // If sourceIsSet2; add the current node to set1, else add it to set2 
                if (sourceIsSet2)
                    set1.Add(current.val);
                else
                    set2.Add(current.val);

                // Parse through all adjacent Nodes
                foreach (Node adj in current.adjacent)
                {
                    // If self directed, it's not a bipartite graph
                    if (current.val == adj.val)
                    {
                        return false;
                    }

                    // Quit execution only if a false condition is encountered, else propogate
                    if (!IsBipartite(adj, set1, set2, !sourceIsSet2))
                        return false;
                }
                return true;
            }