Número mínimo de días necesarios para programar todos los exámenes

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.

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)

Publicación traducida automáticamente

Artículo escrito por rudranger y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *