Dado un gráfico que consta de N Nodes, donde cada Node representa un examen y una array 2D Edges[][2] tal que cada par del examen (Edges[i][0], Edges[i][1]) denota el borde entre ellos, la tarea es encontrar la cantidad mínima de días necesarios para programar todos los exámenes de modo que no se programen dos exámenes conectados a través de un borde en el mismo día.
Ejemplos:
Entrada: N = 5, E = 10, Bordes[][] = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
Salida: 5
Explicación:
En el gráfico anterior, todos los Nodes (que representan exámenes) están conectados entre sí a través de una ruta dirigida. Por lo tanto, el número mínimo de días necesarios para realizar el examen es de 5.
Entrada: N = 7, E = 12, Bordes[][] = [{0, 1}, {0, 3}, {0, 4}, {0, 6}, {1, 2}, {1, 4}, {1, 6}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {4, 5}]
Salida: 3
Enfoque: El problema dado se puede resolver utilizando el concepto de coloración de gráficos . Aunque el problema es NP completo, una buena aproximación es la siguiente.
- Cree una array de adyacencia a partir de los Edges[][] dados del gráfico .
- Inicialice un vector de pares , digamos vdegree[] que almacena el grado de cada Node con Nodes.
- Calcula el grado de cada vértice y guárdalo en la array vdegree[] .
- Organice todos los vértices en vdegree[] en orden descendente de grado.
- Inicialice dos arrays, diga color[] y coloreado[] para almacenar los colores utilizados para colorear los vértices y si un vértice ha sido coloreado o no.
- Inicialice dos variables, digamos numvc y K como 0 , que lleva la cuenta del número de vértices coloreados y el número de color asignado a cada Node.
- Iterar sobre el rango [0, V] usando la variable i y realizar los siguientes pasos:
- Si el valor de numvc es el mismo que el de V , salga del ciclo ya que todos los vértices están coloreados.
- Si el vértice actual está coloreado, continúe con la iteración .
- Si el vértice no está coloreado, colorea el vértice con el color K como coloured[vdegree[i]] = color[K] e incrementa el valor de numvc .
- Itere sobre el rango [0, V] , y si el vértice actual no está coloreado y no es adyacente al Node i , coloree el Node actual con el color K e incremente el valor de numvc .
- Incremente el valor de K en 1 .
- Ordene la array coloreada[] en orden creciente .
- Después de completar los pasos anteriores, imprima el valor de la cantidad de elementos únicos presentes en la array coloreada [] como la cantidad mínima de días.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Comparator function to sort the
// vector of pairs in decreasing order
bool compare(pair<int, int> a,
pair<int, int> b)
{
// If the first values are the same
if (a.first == b.first) {
return (a.second < b.second);
}
// Otherwise
else {
return (a.first > b.first);
}
}
// Function to add an undirected
// edge between any pair of nodes
void addEdge(vector<vector<int> >& adj,
int u, int v)
{
adj[u][v] = 1;
adj[v][u] = 1;
}
// Function to find the minimum number
// of days to schedule all the exams
int minimumDays(int V, int Edges[][2],
int E)
{
// Stores the adjacency list of
// the given graph
vector<vector<int> > adj(
V, vector<int>(V, 0));
// Iterate over the edges
for (int i = 0; i < E; i++) {
int u = Edges[i][0];
int v = Edges[i][1];
// Add the edges between the
// nodes u and v
addEdge(adj, u, v);
}
// Initialize a vector of pair that
// stores { degree, vertex }
vector<pair<int, int> > vdegree(V);
for (int i = 0; i < V; i++) {
// Degree of the node
int degree = 0;
vdegree[i].second = i;
for (int j = 0; j < V; j++) {
if (adj[i][j] != 0) {
// Increment the degree
degree++;
}
}
// Update the degree of the
// current node
vdegree[i].first = degree;
}
// Sort to arrange all vertices
// in descending order of degree
sort(vdegree.begin(),
vdegree.end(), compare);
// Stores the vertices according
// to degree in descending order
int vorder[V];
for (int i = 0; i < V; i++) {
vorder[i] = vdegree[i].second;
}
// Stores the color of the all
// the nodes
int color[V];
for (int i = 0; i < V; i++) {
color[i] = i + 1;
}
int colored[V];
// Initialize all vertices with
// an invalid color 0
memset(colored, 0, sizeof(colored));
// Keeps the track of number of
// vertices colored
int numvc = 0;
// Track the different color
// assigned
int k = 0;
for (int i = 0; i < V; i++) {
// If all vertices are colored
// then exit from the for loop
if (numvc == V) {
break;
}
// If vertex is already
// colored, then continue
if (colored[vorder[i]] != 0) {
continue;
}
// If vertex not colored
else {
colored[vorder[i]] = color[k];
// After coloring increase
// the count of colored
// vertex by 1
numvc++;
for (int j = 0; j < V; j++) {
// If the current node
// and its adjacent are
// not colored
if (colored[j] == 0
&& adj[vorder[i]][j] == 0) {
colored[j] = color[k];
// Increment the count
numvc++;
}
}
// Increment k
k++;
}
}
// Sort the array
sort(colored, colored + V);
// Count of unique colors
int unique_color = 1;
// Count the number of unique
// colors
for (int i = 1; i < V; i++) {
if (colored[i]
!= colored[i - 1]) {
unique_color++;
}
}
// Return the number of days
// to sechedule an exam
return unique_color;
}
// Driver Code
int main()
{
int V = 7, E = 12;
int Edges[][2]
= { { 0, 1 }, { 0, 3 }, { 0, 4 }, { 0, 6 }, { 1, 2 }, { 1, 4 }, { 1, 6 }, { 2, 5 }, { 2, 6 }, { 3, 4 }, { 3, 5 }, { 4, 5 } };
cout << minimumDays(V, Edges, E);
return 0;
}
Python3
# Python 3 program for the above approach # Comparator function to sort the # vector of pairs in decreasing order # Function to add an undirected # edge between any pair of nodes def addEdge(adj, u, v): adj[u][v] = 1 adj[v][u] = 1 # Function to find the minimum number # of days to schedule all the exams def minimumDays(V, Edges, E): # Stores the adjacency list of # the given graph adj = [[0 for i in range(V)] for j in range(V)] # Iterate over the edges for i in range(E): u = Edges[i][0] v = Edges[i][1] # Add the edges between the # nodes u and v addEdge(adj, u, v) # Initialize a vector of pair that # stores [degree, vertex } vdegree = [[0,0] for i in range(V)] for i in range(V): # Degree of the node degree = 0 vdegree[i][1] = i for j in range(V): if (adj[i][j] != 0): # Increment the degree degree += 1 # Update the degree of the # current node vdegree[i][0] = degree # Sort to arrange all vertices # in descending order of degree vdegree.sort(reverse=True) # Stores the vertices according # to degree in descending order vorder = [0 for i in range(V)] for i in range(V): vorder[i] = vdegree[i][1] # Stores the color of the all # the nodes color = [0 for i in range(V)] for i in range(V): color[i] = i + 1 colored = [0 for i in range(V)] # Keeps the track of number of # vertices colored numvc = 0 # Track the different color # assigned k = 0 for i in range(V): # If all vertices are colored # then exit from the for loop if (numvc == V): break # If vertex is already # colored, then continue if (colored[vorder[i]] != 0): continue # If vertex not colored else: colored[vorder[i]] = color[k] # After coloring increase # the count of colored # vertex by 1 numvc += 1 for j in range(V): # If the current node # and its adjacent are # not colored if (colored[j] == 0 and adj[vorder[i]][j] == 0): colored[j] = color[k] # Increment the count numvc += 1 # Increment k k += 1 # Sort the array colored.sort() # Count of unique colors unique_color = 1 # Count the number of unique # colors for i in range(1,V,1): if (colored[i] != colored[i - 1]): unique_color += 1 # Return the number of days # to sechedule an exam return unique_color # Driver Code if __name__ == '__main__': V = 7 E = 12 Edges = [[0, 1 ], [0, 3 ], [0, 4 ], [0, 6 ], [1, 2 ], [1, 4 ], [1, 6 ], [2, 5 ], [2, 6 ], [3, 4 ], [3, 5 ], [4, 5 ] ] print(minimumDays(V, Edges, E)) # This code is contributed by ipg2016107.
Javascript
<script>
// JavaScript program for the above approach
// Comparator function to sort the
// vector of pairs in decreasing order
function compare(a,b)
{
// If the first values are the same
if (a[0] == b[0]) {
return (a[1] - b[1]);
}
// Otherwise
else {
return (a[0] - b[0]);
}
}
// Function to add an undirected
// edge between any pair of nodes
function addEdge(adj,u,v)
{
adj[u][v] = 1;
adj[v][u] = 1;
}
// Function to find the minimum number
// of days to schedule all the exams
function minimumDays(V,Edges,E)
{
// Stores the adjacency list of
// the given graph
let adj = new Array(V);
for(let i=0;i<V;i++)
adj[i] = new Array(V).fill(0);
// Iterate over the edges
for (let i = 0; i < E; i++) {
let u = Edges[i][0];
let v = Edges[i][1];
// Add the edges between the
// nodes u and v
addEdge(adj, u, v);
}
// Initialize a vector of pair that
// stores { degree, vertex }
let vdegree = new Array(V);
for (let i = 0; i < V; i++) {
// Degree of the node
let degree = 0;
vdegree[i] = new Array(2);
vdegree[i][1] = i;
for (let j = 0; j < V; j++) {
if (adj[i][j] != 0) {
// Increment the degree
degree++;
}
}
// Update the degree of the
// current node
vdegree[i].first = degree;
}
// Sort to arrange all vertices
// in descending order of degree
vdegree.sort(compare);
// Stores the vertices according
// to degree in descending order
let vorder = new Array(V);
for (let i = 0; i < V; i++) {
vorder[i] = vdegree[i][1];
}
// Stores the color of the all
// the nodes
let color = new Array(V);
for (let i = 0; i < V; i++) {
color[i] = i + 1;
}
// Initialize all vertices with
// an invalid color 0
let colored = new Array(V).fill(0);
// Keeps the track of number of
// vertices colored
let numvc = 0;
// Track the different color
// assigned
let k = 0;
for (let i = 0; i < V; i++) {
// If all vertices are colored
// then exit from the for loop
if (numvc == V) {
break;
}
// If vertex is already
// colored, then continue
if (colored[vorder[i]] != 0) {
continue;
}
// If vertex not colored
else {
colored[vorder[i]] = color[k];
// After coloring increase
// the count of colored
// vertex by 1
numvc++;
for (let j = 0; j < V; j++) {
// If the current node
// and its adjacent are
// not colored
if (colored[j] == 0
&& adj[vorder[i]][j] == 0) {
colored[j] = color[k];
// Increment the count
numvc++;
}
}
// Increment k
k++;
}
}
// Sort the array
colored.sort();
// Count of unique colors
let unique_color = 1;
// Count the number of unique
// colors
for (let i = 1; i < V; i++) {
if (colored[i]
!= colored[i - 1]) {
unique_color++;
}
}
// Return the number of days
// to sechedule an exam
return unique_color;
}
// Driver Code
let V = 7, E = 12;
let Edges = [ [ 0, 1 ], [ 0, 3 ], [ 0, 4 ], [ 0, 6 ],
[ 1, 2 ], [ 1, 4 ], [ 1, 6 ], [ 2, 5 ], [ 2, 6 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ];
document.write(minimumDays(V, Edges, E),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción:
3
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)