  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Clan War

Last Updated on March 28, 2022 by Ria Pathak ### Concepts Used

Depth First Search, Disjoint Set

Medium

### Problem Statement :

There are two clans numbered sequentially from `1` to `N` and given two integers, `u` and `v` denoting 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 `u` and `v` such that every edge connects a vertex in `u` to one in `v`.

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 (`0` or `1`) 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() :

1. create a queue and push the current vertex now perform following operations untill the queue is empty:
2. each time we pop a vertex `v` from queue, ( `v` = queue.front() ), we will mark the vertex `v` as visited (`visited[v]= true`).
3. Iterate for all the adjacent vertices of `v` and for every adjacent vertex `a`, do following :
• if the colour of the vertex is `-1`, then assign the colour opposite to that of `v`.
• if the colour of `a` and `v` is same, return false.
• if `a` is not visited i.e `visited[a]= false`,
and if `a` has value `1`.
• push the vertex `a` into queue.

### Complexity Analysis:

The time complexity of the first method is represented in the form of `O(V+E)`, where `V` is the number of verices and `E` is the number of edges.

The space complexity of the algorithm is `O(V)` for `visited[]` & `colour[]` array.

### Solutions:

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INT_MIN -99999

struct node {
int vertex;
struct node* next;
};
struct node* createNode(int);

struct Graph {
int numVertices;
};

// 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++)

return graph;
}

void addEdge(struct Graph* graph, int s, int d) {
// Add edge from s to d
struct node* newNode = createNode(d);

// Add edge from d to s
newNode = createNode(s);
}

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

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;

public Graph(int vertices) {
this.vertices = vertices;

//Initialize lists
for (int i = 0; i < vertices; i++) {
}
}

public void addEdge(int source, int destination) {

}

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

//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

while (!queue.isEmpty()) {
int v = queue.remove();
for (int i = 0; i < adjList[v].size(); 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;
}
}
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();

}

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.