Minimize colours to paint graph such that no path have same colour - Coding

Given a directed graph with N nodes and M connections shown in the matrix mat[] where each element is of the form {x_i, y_i} denoting a directed edge from y_i to x_i. The task is to use the minimum number of colours to paint the nodes of the graph such that no two nodes in a path have the same colour.

Examples:

Input: N = 5, M = 6, mat = {{1, 3}, {2, 3}, {3, 4}, {1, 4}, {2, 5}, {3, 5}}
Output: 3
Explanation: The graph nodes can be coloured as shown below
and that is the minimum number of colours possible.

Example 1

Input: N = 3, M = 2, mat = {{1, 3}, {2, 3}}
Output: 2
Explanation: Here 1 and 2 can be assigned same colour and 3 another colour.

Approach: The problem can be solved using the concept of topological sorting as follows:

We can observe that the minimum number of colours required is the same as the length of the longest path of the graph.

All nodes having indegree = 0 can be assigned the same colour. Now remove one indegree from their neighbours and again iterate all the nodes with indegree = 0.

If this is followed, a node will be assigned a colour only when all the other nodes above it in all the paths are assigned a colour. So this will give the maximum length of a path.

Follow the steps below to Implement the Idea:

Create an adjacency list for the directed graph from the given edges.
Maintain an indegree vector to store the indegrees of each node.
Declare a variable (say lvl) to store the depth of a node.
During each iteration of topological sorting a new color is taken and assigned to minions with indegree 0 and in each iteration lvl is incremented by one as a new color is taken.
Return the final value of lvl as the required answer.

Below is the implementation of the above approach:

C++

// C++ code for the above approach: 
  
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to find 
// minimum number of colours required 
int minColour(int N, int M, vector<int> mat[]) 
{ 
    // Create an adjacency list 
    vector<vector<int> > adj(N + 1); 
  
    // Create indeg to store 
    // indegree of every minion 
    vector<int> indeg(N + 1); 
  
    for (int i = 0; i < M; i++) { 
  
        // Store mat[i][1] in adj[(mat[i][0])] 
        // as mat[i][1] directs to mat[1][0] 
        adj[(mat[i][0])].push_back(mat[i][1]); 
        indeg[(mat[i][1])]++; 
    } 
  
    // Initialize a variable lvl to store min 
    // different colors required 
    int lvl = 0; 
    queue<int> q; 
  
    for (int i = 1; i <= N; i++) { 
        if (indeg[i] == 0) { 
            q.push(i); 
        } 
    } 
  
    if (q.empty()) 
        return 0; 
  
    // Loop to use Topological sorting 
    while (!q.empty()) { 
        int size = q.size(); 
        for (int k = 0; k < size; k++) { 
            int e = q.front(); 
            q.pop(); 
  
            for (auto it : adj[e]) { 
                indeg[it]--; 
                if (indeg[it] == 0) { 
                    q.push(it); 
                } 
            } 
        } 
        lvl++; 
    } 
  
    // Return the minimum number of colours 
    return lvl; 
} 
  
// Driver code 
int main() 
{ 
    int N = 5, M = 6; 
    vector<int> mat[] = { { 1, 3 }, { 2, 3 }, { 3, 4 }, { 1, 4 }, { 2, 5 }, { 3, 5 } }; 
  
    // Function Call 
    cout << minColour(N, M, mat); 
    return 0; 
}

Java

// Java code for the above approach: 
  
import java.util.*; 
  
class GFG { 
  
    // Function to find 
    // minimum number of colours required 
    static int minColour(int N, int M, int mat[][]) 
    { 
        // Create an adjacency list 
        Vector<Integer>[] adj = new Vector[N + 1]; 
        for (int i = 0; i < N; i++) 
            adj[i] = new Vector<Integer>(); 
  
        // Create indeg to store 
        // indegree of every minion 
        int[] indeg = new int[M]; 
  
        for (int i = 0; i < M; i++) { 
  
            // Store mat[i][1] in adj[(mat[i][0])] 
            // as mat[i][1] directs to mat[1][0] 
            adj[(mat[i][0])].add(mat[i][1]); 
            indeg[(mat[i][1])]++; 
        } 
  
        // Initialize a variable lvl to store min 
        // different colors required 
        int lvl = 0; 
        Queue<Integer> q = new LinkedList<>(); 
  
        for (int i = 1; i <= N; i++) { 
            if (indeg[i] == 0) { 
                q.add(i); 
            } 
        } 
  
        if (q.isEmpty()) 
            return 0; 
  
        // Loop to use Topological sorting 
        while (!q.isEmpty()) { 
            int size = q.size(); 
            for (int k = 0; k < size; k++) { 
                int e = q.peek(); 
                q.remove(); 
                if (adj[e] != null) 
                    for (int it : adj[e]) { 
                        indeg[it]--; 
                        if (indeg[it] == 0) { 
                            q.add(it); 
                        } 
                    } 
            } 
            lvl++; 
        } 
  
        // Return the minimum number of colours 
        return lvl; 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        int N = 5, M = 6; 
        int[][] mat = { { 1, 3 }, { 2, 3 }, { 3, 4 }, { 1, 4 }, { 2, 5 }, { 3, 5 } }; 
  
        // Function Call 
        System.out.print(minColour(N, M, mat)); 
    } 
} 
  
// This code contributed by shikhasingrajput

Python3

# python code for the above approach: 
  
# Function to find 
# minimum number of colours required 
def minColour(N, M, mat): 
  
    # Create an adjacency list 
    adj = [[] for _ in range(N + 1)] 
  
    # Create indeg to store 
    # indegree of every minion 
    indeg = [0 for _ in range(N + 1)] 
  
    for i in range(0, M): 
  
        # Store mat[i][1] in adj[(mat[i][0])] 
        # as mat[i][1] directs to mat[1][0] 
        adj[(mat[i][0])].append(mat[i][1]) 
        indeg[(mat[i][1])] += 1
  
    # Initialize a variable lvl to store min 
    # different colors required 
    lvl = 0
    q = [] 
  
    for i in range(1, N + 1): 
        if (indeg[i] == 0): 
            q.append(i) 
  
    if (len(q) == 0): 
        return 0
  
    # Loop to use Topological sorting 
    while (len(q) != 0): 
        size = len(q) 
        for k in range(0, size): 
            e = q[0] 
            q.pop(0) 
  
            for it in adj[e]: 
                indeg[it] -= 1
                if (indeg[it] == 0): 
                    q.append(it) 
  
        lvl += 1
  
    # Return the minimum number of colours 
    return lvl 
  
# Driver code 
if __name__ == "__main__": 
  
    N = 5
    M = 6
    mat = [[1, 3], [2, 3], [3, 4], [1, 4], [2, 5], [3, 5]] 
  
    # Function Call 
    print(minColour(N, M, mat)) 
  
# This code is contributed by rakeshsahni 

C#

// C# code for the above approach: 
  
using System; 
using System.Collections.Generic; 
  
class GFG { 
  
    // Function to find 
    // minimum number of colours required 
    static int minColour(int N, int M, int[, ] mat) 
    { 
        // Create an adjacency list 
        List<int>[] adj = new List<int>[N + 1]; 
        for (int i = 0; i < N; i++) 
            adj[i] = new List<int>(); 
  
        // Create indeg to store 
        // indegree of every minion 
        int[] indeg = new int[M]; 
  
        for (int i = 0; i < M; i++) { 
  
            // Store mat[i][1] in adj[(mat[i][0])] 
            // as mat[i][1] directs to mat[1][0] 
            adj[(mat[i, 0])].Add(mat[i, 1]); 
            indeg[(mat[i, 1])]++; 
        } 
  
        // Initialize a variable lvl to store min 
        // different colors required 
        int lvl = 0; 
        List<int> q = new List<int>(); 
  
        for (int i = 1; i <= N; i++) { 
            if (indeg[i] == 0) { 
                q.Add(i); 
            } 
        } 
  
        if (q.Count == 0) 
            return 0; 
  
        // Loop to use Topological sorting 
        while (q.Count != 0) { 
            int size = q.Count; 
            for (int k = 0; k < size; k++) { 
                int e = q[0]; 
                q.RemoveAt(0); 
                if (adj[e] != null) 
                    foreach(int it in adj[e]) 
                    { 
                        indeg[it]--; 
                        if (indeg[it] == 0) { 
                            q.Add(it); 
                        } 
                    } 
            } 
            lvl++; 
        } 
  
        // Return the minimum number of colours 
        return lvl; 
    } 
  
    // Driver code 
    public static void Main(string[] args) 
    { 
        int N = 5, M = 6; 
        int[, ] mat = { { 1, 3 }, { 2, 3 }, { 3, 4 }, { 1, 4 }, { 2, 5 }, { 3, 5 } }; 
  
        // Function Call 
        Console.WriteLine(minColour(N, M, mat)); 
    } 
} 
  
// This code contributed by phasing17

Javascript

// JavaScript code for the above approach: 
  
// Function to find 
// minimum number of colours required 
function minColour(N, M, mat) 
{ 
    // Create an adjacency list 
    let adj = new Array(N + 1); 
    for (var i = 0; i <= N; i++) 
        adj[i] = [];  
  
    // Create indeg to store 
    // indegree of every minion 
    let indeg = new Array(N + 1).fill(0); 
  
    for (var i = 0; i < M; i++) 
    { 
        // Store mat[i][1] in adj[(mat[i][0])] 
        // as mat[i][1] directs to mat[1][0] 
        adj[(mat[i][0])].push(mat[i][1]) 
        indeg[(mat[i][1])] += 1 
    } 
      
      
    // Initialize a variable lvl to store min 
    // different colors required 
    let lvl = 0 
    let q = [] 
  
    for (var i = 1; i <= N; i++) 
    { 
        if (indeg[i] == 0) 
            q.push(i) 
    } 
  
    if (q.length == 0) 
        return 0 
  
    // Loop to use Topological sorting 
    while (q.length != 0) 
    { 
        let size = q.length 
        for (var k = 0; k < size; k++) 
        { 
            let e = q.shift() 
  
            for (var it of adj[e]) 
            { 
                indeg[it] -= 1 
                if (indeg[it] == 0) 
                    q.push(it) 
            } 
        } 
  
        lvl += 1 
    } 
  
    // Return the minimum number of colours 
    return lvl 
} 
  
  
// Driver code 
  
let N = 5 
let M = 6 
let mat = [[1, 3], [2, 3], [3, 4], [1, 4], [2, 5], [3, 5]] 
  
// Function Call 
console.log(minColour(N, M, mat)) 
  
  
// This code is contributed by phasing17 

Output

Time Complexity: O(N + M)
Auxiliary Space: O(N + M)

Reffered: https://www.geeksforgeeks.org

Graph

Related
Applications, Advantages and Disadvantages of Unweighted Graph
Count of nodes accessible from all other nodes of Graph
Applications, Advantages and Disadvantages of Directed Graph
Applications, Advantages and Disadvantages of Graph
Find edges removing which does not disconnect the Graph

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	14