Divide given Graph into Bipartite sets
Given a graph G(V, E), divide it into two sets such that no two vertices in a set are connected directly. If not possible print “Not Possible”.
Examples:
Input: V = 7, E = 6,
Edge = {{1, 2}, {2, 3}, {3, 4}, {3, 6}, {5, 6}, {6, 7}}
Output:
7 5 1 3
6 2 4
Explanation: node {7, 5, 1, 3} are not connected directly and nodes {6, 2, 4} are not connected directly
.Input: V = 3, E = 3,
Edge = {{1, 2}, {2, 3}, {3, 1}}
Output: Not Possible
Explanation: Cannot be divided into two parts
Approach: The idea is to use two sets say (U and V) and traverse the graph in a BFS manner. Traverse each vertex, mark it as visited, check if the neighboring vertices are present in the sets or not. If not, then insert it into the set opposite of the current one. If yes, then if they are in the same set then return false. Follow the steps below to solve the problem:
- Define a function bipartite() and perform the following tasks:
- If V equals 0 then return true.
- Otherwise, perform the BFS to check if neighbors belong to the opposite set or not.
- Initialize the boolean variable res as true.
- Initialize the vector visited[V+1] with values false.
- Iterate over the range [1, V] using the variable i and perform the following tasks:
- If visited[i] is false then set the value of res as bitwise AND of res and bipartite() where the function checks if it is possible to divide.
- After performing the above steps, print the answer.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Unordered sets to store ans unordered_set< int > sets[2]; // Function to divide a graph into two sets, // returns true if possible otherwise false bool bipartite(vector<vector< int > >& edges, int V, int i, vector< bool >& visited) { if (V == 0) { return true ; } vector< int > pending; // Inserting source vertex in U(set[0]) sets[0].insert(i); // Enqueue source vertex pending.push_back(i); while (pending.size() > 0) { // Dequeue current vertex int current = pending.back(); // Mark the current vertex true visited[current] = true ; pending.pop_back(); // Finding the set of // current vertex(parent vertex) int currentSet = sets[0].count(current) > 0 ? 0 : 1; for ( int i = 0; i < edges[current].size(); i++) { // Picking out neighbour // of current vertex int neighbor = edges[current][i]; // If not present // in any of the set if (sets[0].count(neighbor) == 0 && sets[1].count(neighbor) == 0) { // Inserting in opposite // of current vertex sets[1 - currentSet].insert(neighbor); pending.push_back(neighbor); } // Else if present in the same // current vertex set the partition // is not possible else if (sets[currentSet].count(neighbor) > 0) { return false ; } } } return true ; } bool possibleBipartition( int V, vector<vector< int > >& G) { // To store graph as adjacency list in edges vector<vector< int > > edges(V + 1); for ( auto v : G) { edges[v[0]].push_back(v[1]); edges[v[1]].push_back(v[0]); } vector< bool > visited(V + 1, false ); bool res = true ; for ( int i = 1; i <= V; i++) { if (!visited[i]) { res = res and bipartite(edges, V, i, visited); } } return res; } // Driver Code int main() { int V = 7, E = 6; vector<vector< int > > G = { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 3, 6 }, { 5, 6 }, { 6, 7 } }; // If partition is possible if (possibleBipartition(V, G)) { for ( auto elem : sets[0]) { cout << elem << " " ; } cout << "\n" ; for ( auto elem : sets[1]) { cout << elem << " " ; } } // If partition is not possible else cout << "Not Possible" ; return 0; } |
Java
import java.util.*; class GFG { // Unordered sets to store ans static HashSet<Integer>[] sets = new HashSet[ 2 ]; // Function to divide a graph into two sets, // returns true if possible otherwise false static boolean bipartite(ArrayList<ArrayList<Integer>> edges, int V, int i, ArrayList<Boolean> visited) { if (V == 0 ) { return true ; } ArrayList<Integer> pending = new ArrayList<>(); // Inserting source vertex in U(set[0]) sets[ 0 ].add(i); // Enqueue source vertex pending.add(i); while (pending.size() > 0 ) { // Dequeue current vertex int current = pending.get(pending.size()- 1 ); // Mark the current vertex true visited.set(current, true ); pending.remove(pending.size()- 1 ); // Finding the set of // current vertex(parent vertex) int currentSet = sets[ 0 ].contains(current) ? 0 : 1 ; for ( int j = 0 ; j < edges.get(current).size(); j++) { // Picking out neighbour // of current vertex int neighbor = edges.get(current).get(j); // If not present // in any of the set if (!sets[ 0 ].contains(neighbor) && !sets[ 1 ].contains(neighbor)) { // Inserting in opposite // of current vertex sets[ 1 - currentSet].add(neighbor); pending.add(neighbor); } // Else if present in the same // current vertex set the partition // is not possible else if (sets[currentSet].contains(neighbor)) { return false ; } } } return true ; } static boolean possibleBipartition( int V, ArrayList<ArrayList<Integer>> G) { // To store graph as adjacency list in edges ArrayList<ArrayList<Integer>> edges = new ArrayList<>(); for ( int i = 0 ; i <= V; i++) { edges.add( new ArrayList<Integer>()); } for (ArrayList<Integer> v : G) { edges.get(v.get( 0 )).add(v.get( 1 )); edges.get(v.get( 1 )).add(v.get( 0 )); } ArrayList<Boolean> visited = new ArrayList<>(Collections.nCopies(V+ 1 , false )); boolean res = true ; for ( int i = 1 ; i <= V; i++) { if (!visited.get(i)) { res = res && bipartite(edges, V, i, visited); } } return res; } // Driver Code public static void main(String[] args) { int V = 7 , E = 6 ; ArrayList<ArrayList<Integer>> G = new ArrayList<>(); G.add( new ArrayList<>(Arrays.asList( 1 , 2 ))); G.add( new ArrayList<>(Arrays.asList( 2 , 3 ))); G.add( new ArrayList<>(Arrays.asList( 3 , 4 ))); G.add( new ArrayList<>(Arrays.asList( 3 , 6 ))); G.add( new ArrayList<>(Arrays.asList( 5 , 6 ))); G.add( new ArrayList<>(Arrays.asList( 6 , 7 ))); sets[ 0 ] = new HashSet<Integer>(); sets[ 1 ] = new HashSet<Integer>(); // If partition is possible if (possibleBipartition(V, G)) { for ( int elem : sets[ 0 ]) { System.out.print(elem + " " ); } System.out.println(); for ( int s : sets[ 1 ]) { System.out.print(s + " " ); } } // If partition is not possible else { System.out.println( "Not Possible" ); } } } |
Python3
# Python program for the above approach # import necessary library import itertools # Unordered sets to store ans sets = [ set (), set ()] # Function to divide a graph into two sets, # returns true if possible otherwise false def bipartite(edges, V, i, visited): if V = = 0 : return True pending = [] # Inserting source vertex in U(set[0]) sets[ 0 ].add(i) # Enqueue source vertex pending.append(i) while pending: # Dequeue current vertex current = pending.pop() # Mark the current vertex true visited[current] = True # Finding the set of # current vertex(parent vertex) currentSet = 0 if current in sets[ 0 ] else 1 for neighbor in edges[current]: # If not present # in any of the set if neighbor not in sets[ 0 ] and neighbor not in sets[ 1 ]: # Inserting in opposite # of current vertex sets[ 1 - currentSet].add(neighbor) pending.append(neighbor) # Else if present in the same # current vertex set the partition # is not possible elif neighbor in sets[currentSet]: return False return True def possibleBipartition(V, G): # To store graph as adjacency list in edges edges = [[] for _ in range (V + 1 )] for u, v in G: edges[u].append(v) edges[v].append(u) visited = [ False ] * (V + 1 ) res = True for i in range ( 1 , V + 1 ): if not visited[i]: res = res and bipartite(edges, V, i, visited) return res # Driver Code if __name__ = = '__main__' : V = 7 G = [[ 1 , 2 ], [ 2 , 3 ], [ 3 , 4 ], [ 3 , 6 ], [ 5 , 6 ], [ 6 , 7 ]] # If partition is possible if possibleBipartition(V, G): print ( * sets[ 0 ]) print ( * sets[ 1 ]) # If partition is not possible else : print ( "Not Possible" ) |
Javascript
// Unordered sets to store ans const sets = [{}, {}]; // Function to divide a graph into two sets, // returns true if possible otherwise false function bipartite(edges, V, i, visited) { if (V == 0) { return true ; } const pending = []; // Inserting source vertex in U(set[0]) sets[0][i] = true ; // Enqueue source vertex pending.push(i); while (pending.length > 0) { // Dequeue current vertex const current = pending.pop(); // Mark the current vertex true visited[current] = true ; // Finding the set of current vertex(parent vertex) const currentSet = current in sets[0] ? 0 : 1; for (let i = 0; i < edges[current].length; i++) { // Picking out neighbour of current vertex const neighbor = edges[current][i]; // If not present in any of the set if (!(neighbor in sets[0]) && !(neighbor in sets[1])) { // Inserting in opposite of current vertex sets[1 - currentSet][neighbor] = true ; pending.push(neighbor); } // Else if present in the same current vertex set // the partition is not possible else if (neighbor in sets[currentSet]) { return false ; } } } return true ; } function possibleBipartition(V, G) { // To store graph as adjacency list in edges const edges = new Array(V + 1).fill().map(() => []); for (const v of G) { edges[v[0]].push(v[1]); edges[v[1]].push(v[0]); } const visited = new Array(V + 1).fill( false ); let res = true ; for (let i = 1; i <= V; i++) { if (!visited[i]) { res = res && bipartite(edges, V, i, visited); } } return res; } // Driver Code const V = 7, E = 6; const G = [[1, 2], [2, 3], [3, 4], [3, 6], [5, 6], [6, 7]]; // If partition is possible if (possibleBipartition(V, G)) { console.log( "Set 1:" , Object.keys(sets[0]).join( " " )); console.log( "Set 2:" , Object.keys(sets[1]).join( " " )); } // If partition is not possible else { console.log( "Not Possible" ); } |
C#
using System; using System.Collections.Generic; public class GFG { // Unordered sets to store ans static HashSet< int >[] sets = new HashSet< int >[2]; // Function to divide a graph into two sets, // returns true if possible otherwise false static bool Bipartite(List<List< int >> edges, int V, int i, bool [] visited) { if (V == 0) { return true ; } List< int > pending = new List< int >(); // Inserting source vertex in U(set[0]) sets[0].Add(i); // Enqueue source vertex pending.Add(i); while (pending.Count > 0) { // Dequeue current vertex int current = pending[pending.Count - 1]; // Mark the current vertex true visited[current] = true ; pending.RemoveAt(pending.Count - 1); // Finding the set of current vertex(parent vertex) int currentSet = sets[0].Contains(current) ? 0 : 1; foreach ( int neighbor in edges[current]) { // If not present in any of the set if (!sets[0].Contains(neighbor) && !sets[1].Contains(neighbor)) { // Inserting in opposite of current vertex sets[1 - currentSet].Add(neighbor); pending.Add(neighbor); } // Else if present in the same // current vertex set the partition // is not possible else if (sets[currentSet].Contains(neighbor)) { return false ; } } } return true ; } public static bool PossibleBipartition( int V, List<List< int >> G) { // To store graph as adjacency list in edges List<List< int >> edges = new List<List< int >>(); for ( int i = 0; i <= V; i++) { edges.Add( new List< int >()); } foreach (List< int > v in G) { edges[v[0]].Add(v[1]); edges[v[1]].Add(v[0]); } bool [] visited = new bool [V + 1]; bool res = true ; for ( int i = 1; i <= V; i++) { if (!visited[i]) { res = res && Bipartite(edges, V, i, visited); } } return res; } public static void Main() { int V = 7, E = 6; List<List< int >> G = new List<List< int >>(); G.Add( new List< int > { 1, 2 }); G.Add( new List< int > { 2, 3 }); G.Add( new List< int > { 3, 4 }); G.Add( new List< int > { 3, 6 }); G.Add( new List< int > { 5, 6 }); G.Add( new List< int > { 6, 7 }); sets[0] = new HashSet< int >(); sets[1] = new HashSet< int >(); // If partition is possible if (PossibleBipartition(V, G)) { foreach ( int elem in sets[0]) { Console.Write(elem + " " ); } Console.WriteLine(); foreach ( int elem in sets[1]) { Console.Write(elem + " " ); } } // If partition is not possible else { Console.Write( "Not Possible" ); } } } |
7 5 1 3 6 2 4
Time Complexity: O(N)
Auxiliary Space: O(N)