Minimice los colores para pintar el gráfico de modo que ninguna ruta tenga el mismo color

Ejemplos:

Entrada:  N = 5, M = 6, mat = {{1, 3}, {2, 3}, {3, 4}, {1, 4}, {2, 5}, {3, 5}}
Salida : 3
Explicación: Los Nodes del gráfico se pueden colorear como se muestra a continuación
y esa es la cantidad mínima de colores posible.
 

Ejemplo 1

Entrada: N = 3, M = 2, mat = {{1, 3}, {2, 3}}
Salida: 2
Explicación: Aquí 1 y 2 se pueden asignar del mismo color y 3 de otro color.

Enfoque: el problema se puede resolver utilizando el concepto de clasificación topológica de la siguiente manera:

Podemos observar que el número mínimo de colores requerido es igual a la longitud del camino más largo del gráfico.

A todos los Nodes que tengan un grado = 0 se les puede asignar el mismo color. Ahora elimine un grado de entrada de sus vecinos y vuelva a iterar todos los Nodes con grado de entrada = 0.

Si se sigue esto, a un Node se le asignará un color solo cuando a todos los demás Nodes por encima de él en todas las rutas se les asigne un color. Así que esto dará la longitud máxima de un camino.

Siga los pasos a continuación para implementar la idea:

• Cree una lista de adyacencia para el gráfico dirigido desde los bordes dados.
• Mantenga un vector de grado de entrada para almacenar los grados de entrada de cada Node.
• Declare una variable (por ejemplo, lvl ) para almacenar la profundidad de un Node.
• Durante cada iteración de clasificación topológica, se toma un nuevo color y se asigna a los minions con un grado de entrada 0 y en cada iteración, lvl se incrementa en uno a medida que se toma un nuevo color.
• Devuelve el valor final de lvl como la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

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

3

Complejidad temporal: O(N + M)
Espacio auxiliar: O(N + M)