Concepts Used

Depth First Search, Disjoint Set

Difficulty Level

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 visit some best sites to learn coding 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

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


        }

    }

Previous post Count Components
Next post Graph Tree

Leave a Reply

Your email address will not be published. Required fields are marked *