Concepts Used

Back Tracking

Difficulty Level

Medium

Problem Statement :

Given an undirected graph and M colors, the problem is to find if it is possible to color the graph with at most M colors or not.

See original problem statement here

Solution Approach :

Introduction :

Idea is to assign different colors (1-M) to all the adjacent vertices. If at any point the color of any two adjacent vertices are same then we say it is not possible, otherwise it is.

Description:

We will use backtracking to solve the above problem.
Backtracking is the approach to solve the problem by testing all possible combinations. If any subproblem does not fit the given constraint then we discard the complete subproblem (backtrack), moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.
We will take a color array color[] to store M colours. Now iterate through color[] , then we will assign each colour to all vertices one-by-one. If any colour assignment does not match the constraints then we will backtrack and unassign the colour which has been assigned to the vertex earlier. If the vertex count reaches the total number of vertices we will return true, and if none of the assignment matches the given condition (adjacent vertices must have different colours) then we will return false.

Algorithm :

colour():

  1. If index == number.of.vertices, return TRUE.
  2. else, for every k= 1 to M :
    • assign color to the current vertex, v, (color[v]=k)
    • if colour(graph,vertex+1,color)==TRUE, return true
    • else ,
    • mark the colour as unassigned, (colour[v]=0) (backtracking step).
    • If none of the combination satisfies, return FALSE.

Complexity Analysis :

According to the fundamentals of data structures in c++ In this method each vertex has M different choices of colors. So the total time complexity is M^V, where M is the number of colours and V is the number of vertices.

Solutions:

 #include <stdio.h>
    int V;


    int isSafe(int v, int graph[V][V],int color[], int c) 
    { 
        for (int i = 0; i < V; i++) 
            if ( 
                graph[v][i] && c == color[i]) 
                return 0; 
        return 1; 
    } 


    int colour(int graph[V][V], int m,int color[], int v) 
    { 

        if (v == V) 
            return 1; 

        for (int c = 1; c <= m; c++) 
        { 
            if (isSafe( 
                    v, graph, color, c)) { 
                color[v] = c; 


                if ( colour(graph, m, color, v + 1)== 1) 
                    return 1; 

                color[v] = 0; 
            } 
        } 

        return 0; 
    } 


    int graphColoring(int graph[V][V], int m) 
    { 

        int color[V]; 
        for (int i = 0; i < V; i++) 
            color[i] = 0; 


        if ( 
            colour(graph, m, color, 0)== 0) { 
            return 0; 
        } 

        return 1; 
    } 


    int main() 
    { 
        int t;
        scanf("%d",&t);
        while(t--)
        {
          int e;
          scanf("%d %d",&V,&e);
          int graph[V][V];
          for(int i=0;i<V;i++)
          {
            for(int j=0;j<V;j++)
             graph[i][j]=0;
          }
          while(e--)
          {
            int u,v;
            scanf("%d %d",&u,&v);
            graph[u][v]=1;
            graph[v][u]=1;
          }
          int m; // Number of colors 
          scanf("%d",&m);
          printf("%d\n",graphColoring(graph, m)); 
        }
        return 0; 
    } 
#include<iostream>
        #define V 100

        using namespace std;


        int isSafe(int v, int graph[V][V],int color[], int c) 
        { 
            for (int i = 0; i < V; i++) 
                if ( 
                    graph[v][i] && c == color[i]) 
                    return 0; 
            return 1; 
        } 


        int colour(int graph[V][V], int m,int color[], int v) 
        { 

            if (v == V) 
                return 1; 

            for (int c = 1; c <= m; c++) 
            { 
                if (isSafe( 
                        v, graph, color, c)) { 
                    color[v] = c; 


                    if ( colour(graph, m, color, v + 1)== 1) 
                        return 1; 

                    color[v] = 0; 
                } 
            } 

            return 0; 
        } 


        int graphColoring(int graph[V][V], int m) 
        { 

            int color[V]; 
            for (int i = 0; i < V; i++) 
                color[i] = 0; 


            if ( 
                colour(graph, m, color, 0)== 0) { 
                return 0; 
            } 

            return 1; 
        } 


        int main() 
        { 
            int t;
            cin>>t;
            while(t--)
            {
            int n,e;
            cin>>n>>e;
            int graph[V][V];
            for(int i=0;i<V;i++)
            {
            for(int j=0;j<V;j++)
            graph[i][j]=0;
            }
            while(e--)
            {
            int u,v;
            cin>>u>>v;
            graph[u][v]=1;
            graph[v][u]=1;
            }
            int m; // Number of colors 
            cin>>m;
            cout<<graphColoring(graph, m)<<endl; 
            }
        return 0; 
    } 
import java.util.*;
    import java.io.*;

    public class Main{ 
        final int V = 100; 
        int color[]; 

        boolean isSafe( 
            int v, int graph[][], int color[], 
            int c) 
        { 
            for (int i = 0; i < V; i++) 
                if ( 
                    graph[v][i] == 1 && c == color[i]) 
                    return false; 
            return true; 
        } 

        boolean graphColoringUtil(    int graph[][], int m,int color[], int v) 
        { 

            if (v == V) 
                return true; 

            for (int c = 1; c <= m; c++) { 

                if (isSafe(v, graph, color, c)) { 
                    color[v] = c; 

                    if ( 
                        graphColoringUtil( 
                            graph, m, 
                            color, v + 1)) 
                        return true; 


                    color[v] = 0; 
                } 
            } 


            return false; 
        } 


        boolean graphColoring(int graph[][], int m) 
        { 

            color = new int[V]; 
            for (int i = 0; i < V; i++) 
                color[i] = 0; 

            if ( 
                !graphColoringUtil( 
                    graph, m, color, 0)) { 

                return false; 
            } 

            return true; 
        } 


        public static void main(String args[]) 
        { 
            Main m = new Main();
        Scanner sc= new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0)
        {
        int n = sc.nextInt();
        int e = sc.nextInt();
        int [][]graph = new int [m.V][m.V];
        for(int i=0;i<m.V;i++)
        {
            for(int j = 0; j<m.V;j++)
            {
            graph[i][j]=0;
            }
        }

        while(e-->0)
        {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u][v]=1;
            graph[v][u]=1;
        }
            int no = sc.nextInt();
            if(m.graphColoring(graph, no)==false)
            System.out.println("0");
            else
            System.out.println("1");
        }
      } 
    } 
Previous post Furious Teacher
Next post Possible Attack-1

Leave a Reply

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