Last Updated on March 28, 2022 by Ria Pathak
Concepts Used
Depth First Search, Disjoint Set
Difficulty Level
Medium
Problem Statement :
There are two clans numbered sequentially from
1toNand given two integers,uandvdenoting the clan numbers that are fighting each other. We assume that the clans of one nation do not fight each other, they only fight with the clans of the enemy nation. Check whether this assumption is correct or not.
See original problem statement here
Solution Approach :
Introduction :
Idea is to seperate clans that fight each other, into two groups. Now we have to check whether any clan fights any clan of the same group, if so our assumption is wrong otherwise it is right.
There is a graph type which can be applied in this problem, "Biparted Graph". A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets
uandvsuch that every edge connects a vertex inuto one inv.Now we just have to check whether our graph is biparted or not.
Below we are going to discuss few approaches to solve this problem.
Method 1 :
We can assign colours (
0or1) to determine which group does the vertex belong. We can simply run dfs from a vertex and assign some colour to each new vertex visited. If the parent’s colour is 1, then all its children must be assigned 0. Now if you encounter a visited node having the same colour as it’s parent, the graph isn’t bipartite.
Method 2 :
Given a graph represented as an adjacency-list (i.e. a list of edges), you can determine if it’s bipartite as follows:
- Initialize a disjoint-set data structure SETS, with a singleton set for each vertex. (If there is an even-length path between two vertices, then we will ultimately unify those two vertices into the same set, unless we return ꜰᴀʟꜱᴇ first.)
- Initialize a parent[ ] for each vertex to ɴɪʟ. (As we examine edges, we will update parent[ ] for each vertex to one of its neighbors.)
- For each edge {u, v}:
If u and v belong to the same parent in SETS, then return ꜰᴀʟꜱᴇ.- If parent[u] = ɴɪʟ, set parent[u] := v.
Otherwise, update SETS to unify v with parent[u].- If parent[v] = ɴɪʟ, set parent[v] := u.
Otherwise, update SETS to unify u with parent[v].- Return ᴛʀᴜᴇ.
Notice that we are returning false as soon as we find a odd length cycle as the odd length cycle can never be divided into two distinct sets. (Think why?).
Algorithms :
dfs() :
- create a queue and push the current vertex now perform following operations untill the queue is empty:
- each time we pop a vertex
vfrom queue, (v= queue.front() ), we will mark the vertexvas visited (visited[v]= true).- Iterate for all the adjacent vertices of
vand for every adjacent vertexa, do following :
- if the colour of the vertex is
-1, then assign the colour opposite to that ofv.- if the colour of
aandvis same, return false.- if
ais not visited i.evisited[a]= false,
and ifahas value1.- push the vertex
ainto queue.
Complexity Analysis:
The time complexity of the first method is represented in the form of
O(V+E), whereVis the number of verices andEis the number of edges.The space complexity of the algorithm is
O(V)forvisited[]&colour[]array.
Solutions:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INT_MIN -99999
//ADJACENCY LIST
struct node {
int vertex;
struct node* next;
};
struct node* createNode(int);
struct Graph {
int numVertices;
struct node** adjLists;
};
// Create a node
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Create a graph
struct Graph* createAGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct node*));
int i;
for (i = 0; i < vertices; i++)
graph->adjLists[i] = NULL;
return graph;
}
// Add edge
void addEdge(struct Graph* graph, int s, int d) {
// Add edge from s to d
struct node* newNode = createNode(d);
newNode->next = graph->adjLists[s];
graph->adjLists[s] = newNode;
// Add edge from d to s
newNode = createNode(s);
newNode->next = graph->adjLists[d];
graph->adjLists[d] = newNode;
}
//QUEUE
struct Queue
{
int front, rear, size;
unsigned capacity;
int* array;
};
struct Queue* createQueue(unsigned capacity)
{
struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1; // This is important, see the enqueue
queue->array = (int*) malloc(queue->capacity * sizeof(int));
return queue;
}
// Queue is empty when size is 0
int isEmpty(struct Queue* queue)
{ return (queue->size == 0); }
// Function to add an item to the queue.
// It changes rear and size
void enqueue(struct Queue* queue, int item)
{
if (isFull(queue))
return;
queue->rear = (queue->rear + 1)%queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
//printf("%d enqueued to queue\n", item);
}
// Function to remove an item from queue.
// It changes front and size
int dequeue(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1)%queue->capacity;
queue->size = queue->size - 1;
return item;
}
// Function to get front of queue
int front(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
int BFS(struct Graph* graph,int n)
{
int visited[n+1];
int colour[n+1];
int node,flag=0;
memset(visited,0,sizeof(visited));
memset(colour,-1,sizeof(colour));
for(int k=0; k<n ;k++)
{
if(!visited[k])
{
struct Queue* q = createQueue(100000);
enqueue(q, k);
colour[k] = 1;
while(!isEmpty(q))
{
node = front(q);
dequeue(q);
// printf("%d ",node);
visited[node] = 1;
struct node* temp = graph->adjLists[node];
//printf("\n Vertex %d\n: ", v);
while (temp) {
// printf("%d ", temp->vertex);
if(colour[temp->vertex] == -1)
colour[temp->vertex] = !colour[node];
else if (colour[temp->vertex] == colour[node])
{
flag = 1;
break;
}
if(!visited[temp->vertex])
enqueue(q,temp->vertex);
temp = temp->next;
}
if(flag)
break;
}
}
if(flag)
break;
}
return flag;
}
int main() {
int t,n,m,u,v;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
struct Graph* graph = createAGraph(n);
//vector<int> graph[n+1];
for(int i=0; i<m; ++i)
{
scanf("%d %d",&u,&v);
// u +=1;
// v +=1;
addEdge(graph, u,v);
}
if(BFS(graph,n))
printf("No\n");
else
printf("Yes\n");
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int BFS(vector<int> graph[],int n)
{
bool visited[n+1];
int colour[n+1];
int node,flag=0;
memset(visited,0,sizeof(visited));
memset(colour,-1,sizeof(colour));
for(int k=1; k<=n ;++k)
{
if(!visited[k])
{
queue<int> q;
q.push(k);
colour[k] = 1;
while(!q.empty())
{
node = q.front();
q.pop();
visited[node] = true;
for(int i=0; i<graph[node].size(); ++i)
{
if(colour[graph[node][i]] == -1)
colour[graph[node][i]] = !colour[node];
else if (colour[graph[node][i]] == colour[node])
{
flag = 1;
break;
}
if(!visited[graph[node][i]])
q.push(graph[node][i]);
}
if(flag)
break;
}
}
if(flag)
break;
}
return flag;
}
int main() {
ios::sync_with_stdio(false);
int t,n,m,u,v;
cin>>t;
while(t--)
{
cin>>n>>m;
vector<int> graph[n+1];
for(int i=0; i<m; ++i)
{
cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
}
if(BFS(graph,n))
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
return 0;
}
import java.util.*;
public class Main {
enum Color{
WHITE, RED, GREEN
}
static class Graph {
int vertices;
LinkedList<Integer>[] adjList;
public Graph(int vertices) {
this.vertices = vertices;
adjList = new LinkedList[vertices];
//Initialize lists
for (int i = 0; i < vertices; i++) {
adjList[i] = new LinkedList<>();
}
}
public void addEdge(int source, int destination) {
//add forward edge
adjList[source].addFirst(destination);
//add back edge
adjList[destination].addFirst(source);
}
public boolean isBipartite(Graph graph) {
//check if graph is empty
if (graph.vertices == 0)
return true;
//initialize colors for all vertices
Color colors[] = new Color[vertices];
//color all the vertices with white color
for (int i = 0; i < colors.length; i++) {
colors[i] = Color.WHITE;
}
Queue<Integer> queue = new LinkedList<>();
//start coloring vertices , this code will handle the disconnected graph as well
//color the first vertex with RED
for (int source = 0; source < vertices; source++) {
if (colors[source] == Color.WHITE) {
colors[source] = Color.RED;
//add it to queue for BFS
queue.add(source);
while (!queue.isEmpty()) {
int v = queue.remove();
for (int i = 0; i < adjList[v].size(); i++) {
int dest = adjList[v].get(i);
if (colors[dest] == Color.WHITE) {
if (colors[v] == Color.RED) {
colors[dest] = Color.GREEN;
}
else if (colors[v] == Color.GREEN)
{
colors[dest] = Color.RED;
}
queue.add(dest);
}
else if (colors[v] == colors[dest]) {
return false;
}
}
}
}
}
return true;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0)
{
int n = sc.nextInt();
int e = sc.nextInt();
Graph graph = new Graph(n);
while(e-->0)
{
int u = sc.nextInt();
int v = sc.nextInt();
graph.addEdge(u,v);
}
boolean result = graph.isBipartite(graph);
if(result)
System.out.println("Yes");
else
System.out.println("No");
}
}
}
[forminator_quiz id="1930"]
This article tried to discuss Depth First Search, Disjoint Set. Hope this blog helps you understand and solve the problem. To practice more problems on Depth First Search, Disjoint Set you can check out MYCODE | Competitive Programming.