Dado un gráfico no dirigido que consta de N vértices y M aristas, donde los valores de los Nodes están en el rango [1, N] y los vértices especificados por la array de color [] están coloreados, la tarea es encontrar el color mínimo de todos los vértices del dado. grafico. El costo de colorear un vértice viene dado por vCost y el costo de agregar un nuevo borde entre dos vértices viene dado por eCost . Si se colorea un vértice, todos los vértices a los que se puede llegar desde ese vértice también se colorean.
Ejemplos:
Entrada: N = 3, M = 1, vCost = 3, eCost = 2, coloreado[] = {1}, fuente[] = {1} destino[] = {2}
Salida: 2
Explicación:
el vértice 1 está coloreado y tiene una arista con 2.
Entonces, el vértice 2 también está coloreado.
Añade una ventaja entre 2 y 3, con un coste de eCost. < vCoste.
Por lo tanto, la salida es 2.Entrada: N = 4, M = 2, vCost = 3, eCost = 7, coloreado[] = {1, 3}, fuente[] = {1, 2} destino[] = {4, 3}
Salida: 0
Explicación :
El vértice 1 está coloreado y tiene una arista con 4. Por lo tanto, el vértice 4 también está coloreado.
El vértice 2 está coloreado y tiene una arista con 3. Por lo tanto, el vértice 3 también está coloreado.
Dado que todos los vértices ya están coloreados, el costo es 0.
Enfoque:
la idea es contar el número de subgráficos de vértices no coloreados utilizando DFS Traversal .
Para minimizar el costo de colorear un Subgraph no coloreado , se debe realizar una de las siguientes acciones :
- Colorea el subgrafo
- Agregue un borde entre cualquier vértice coloreado y sin color.
Según el mínimo de eCost y vCost , se debe elegir uno de los dos pasos anteriores.
Si el número de subgráficos no coloreados viene dado por X , entonces el costo total de colorear todos los vértices viene dado por X×min(eCost, vCost) .
Siga los pasos a continuación para encontrar el número de subgráficos sin color:
- Realice DFS Traversal en todos los vértices coloreados y márquelos visitados para identificarlos como coloreados.
- Los vértices que no se visitan después de DFS en el paso 1 son los vértices sin color.
- Para cada vértice sin color, marque todos los vértices a los que se puede llegar desde ese vértice como visitados mediante DFS.
- El número de vértices no coloreados para los que se produce el DFS en el paso 3 es el número de subgráficos X.
- Calcula el costo total de colorear todos los vértices con la fórmula X×min(eCost, vCost).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to implement DFS Traversal
// to marks all the vertices visited
// from vertex U
void DFS(int U, int* vis, vector<int> adj[])
{
// Mark U as visited
vis[U] = 1;
// Traverse the adjacency list of U
for (int V : adj[U]) {
if (vis[V] == 0)
DFS(V, vis, adj);
}
}
// Function to find the minimum cost
// to color all the vertices of graph
void minCost(int N, int M, int vCost,
int eCost, int sorc[],
vector<int> colored,
int destination[])
{
// To store adjacency list
vector<int> adj[N + 1];
// Loop through the edges to
// create adjacency list
for (int i = 0; i < M; i++) {
adj[sorc[i]].push_back(destination[i]);
adj[destination[i]].push_back(sorc[i]);
}
// To check if a vertex of the
// graph is visited
int vis[N + 1] = { 0 };
// Mark visited to all the vertices
// that can be reached by
// colored vertices
for (int i = 0; i < colored.size(); i++) {
// Perform DFS
DFS(colored[i], vis, adj);
}
// To store count of uncolored
// sub-graphs
int X = 0;
// Loop through vertex to count
// uncolored sub-graphs
for (int i = 1; i <= N; i++) {
// If vertex not visited
if (vis[i] == 0) {
// Increase count of
// uncolored sub-graphs
X++;
// Perform DFS to mark
// visited to all vertices
// of current sub-graphs
DFS(i, vis, adj);
}
}
// Calculate minimum cost to color
// all vertices
int mincost = X * min(vCost, eCost);
// Print the result
cout << mincost << endl;
}
// Driver Code
int main()
{
// Given number of
// vertices and edges
int N = 3, M = 1;
// Given edges
int sorc[] = { 1 };
int destination[] = { 2 };
// Given cost of coloring
// and adding an edge
int vCost = 3, eCost = 2;
// Given array of
// colored vertices
vector<int> colored = { 1};
minCost(N, M, vCost, eCost,
sorc, colored, destination);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to implement DFS Traversal
// to marks all the vertices visited
// from vertex U
static void DFS(int U, int[] vis,
ArrayList<ArrayList<Integer>> adj)
{
// Mark U as visited
vis[U] = 1;
// Traverse the adjacency list of U
for(Integer V : adj.get(U))
{
if (vis[V] == 0)
DFS(V, vis, adj);
}
}
// Function to find the minimum cost
// to color all the vertices of graph
static void minCost(int N, int M, int vCost,
int eCost, int sorc[],
ArrayList<Integer> colored,
int destination[])
{
// To store adjacency list
ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
for(int i = 0; i < N + 1; i++)
adj.add(new ArrayList<Integer>());
// Loop through the edges to
// create adjacency list
for(int i = 0; i < M; i++)
{
adj.get(sorc[i]).add(destination[i]);
adj.get(destination[i]).add(sorc[i]);
}
// To check if a vertex of the
// graph is visited
int[] vis = new int[N + 1];
// Mark visited to all the vertices
// that can be reached by
// colored vertices
for(int i = 0; i < colored.size(); i++)
{
// Perform DFS
DFS(colored.get(i), vis, adj);
}
// To store count of uncolored
// sub-graphs
int X = 0;
// Loop through vertex to count
// uncolored sub-graphs
for(int i = 1; i <= N; i++)
{
// If vertex not visited
if (vis[i] == 0)
{
// Increase count of
// uncolored sub-graphs
X++;
// Perform DFS to mark
// visited to all vertices
// of current sub-graphs
DFS(i, vis, adj);
}
}
// Calculate minimum cost to color
// all vertices
int mincost = X * Math.min(vCost, eCost);
// Print the result
System.out.println(mincost);
}
// Driver code
public static void main(String[] args)
{
// Given number of
// vertices and edges
int N = 3, M = 1;
// Given edges
int sorc[] = {1};
int destination[] = {2};
// Given cost of coloring
// and adding an edge
int vCost = 3, eCost = 2;
// Given array of
// colored vertices
ArrayList<Integer> colored = new ArrayList<>();
colored.add(1);
minCost(N, M, vCost, eCost, sorc,
colored, destination);
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach # Function to implement DFS Traversal # to marks all the vertices visited # from vertex U def DFS(U, vis, adj): # Mark U as visited vis[U] = 1 # Traverse the adjacency list of U for V in adj[U]: if (vis[V] == 0): DFS(V, vis, adj) # Function to find the minimum cost # to color all the vertices of graph def minCost(N, M, vCost, eCost, sorc, colored, destination): # To store adjacency list adj = [[] for i in range(N + 1)] # Loop through the edges to # create adjacency list for i in range(M): adj[sorc[i]].append(destination[i]) adj[destination[i]].append(sorc[i]) # To check if a vertex of the # graph is visited vis = [0] * (N + 1) # Mark visited to all the vertices # that can be reached by # colored vertices for i in range(len(colored)): # Perform DFS DFS(colored[i], vis, adj) # To store count of uncolored # sub-graphs X = 0 # Loop through vertex to count # uncolored sub-graphs for i in range(1, N + 1): # If vertex not visited if (vis[i] == 0): # Increase count of # uncolored sub-graphs X += 1 # Perform DFS to mark # visited to all vertices # of current sub-graphs DFS(i, vis, adj) # Calculate minimum cost to color # all vertices mincost = X * min(vCost, eCost) # Print the result print(mincost) # Driver Code if __name__ == '__main__': # Given number of # vertices and edges N = 3 M = 1 # Given edges sorc = [1] destination = [2] # Given cost of coloring # and adding an edge vCost = 3 eCost = 2 # Given array of # colored vertices colored = [1] minCost(N, M, vCost, eCost, sorc, colored, destination) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to implement DFS Traversal
// to marks all the vertices visited
// from vertex U
static void DFS(int U, int[] vis, ArrayList adj)
{
// Mark U as visited
vis[U] = 1;
// Traverse the adjacency list of U
foreach(int V in (ArrayList)adj[U])
{
if (vis[V] == 0)
DFS(V, vis, adj);
}
}
// Function to find the minimum cost
// to color all the vertices of graph
static void minCost(int N, int M, int vCost,
int eCost, int []sorc,
ArrayList colored,
int []destination)
{
// To store adjacency list
ArrayList adj = new ArrayList();
for(int i = 0; i < N + 1; i++)
adj.Add(new ArrayList());
// Loop through the edges to
// create adjacency list
for(int i = 0; i < M; i++)
{
((ArrayList)adj[sorc[i]]).Add(destination[i]);
((ArrayList)adj[destination[i]]).Add(sorc[i]);
}
// To check if a vertex of the
// graph is visited
int[] vis = new int[N + 1];
// Mark visited to all the vertices
// that can be reached by
// colored vertices
for(int i = 0; i < colored.Count; i++)
{
// Perform DFS
DFS((int)colored[i], vis, adj);
}
// To store count of uncolored
// sub-graphs
int X = 0;
// Loop through vertex to count
// uncolored sub-graphs
for(int i = 1; i <= N; i++)
{
// If vertex not visited
if (vis[i] == 0)
{
// Increase count of
// uncolored sub-graphs
X++;
// Perform DFS to mark
// visited to all vertices
// of current sub-graphs
DFS(i, vis, adj);
}
}
// Calculate minimum cost to color
// all vertices
int mincost = X * Math.Min(vCost, eCost);
// Print the result
Console.Write(mincost);
}
// Driver code
public static void Main(string[] args)
{
// Given number of
// vertices and edges
int N = 3, M = 1;
// Given edges
int []sorc = {1};
int []destination = {2};
// Given cost of coloring
// and adding an edge
int vCost = 3, eCost = 2;
// Given array of
// colored vertices
ArrayList colored = new ArrayList();
colored.Add(1);
minCost(N, M, vCost, eCost,
sorc, colored,
destination);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to implement DFS Traversal
// to marks all the vertices visited
// from vertex U
function DFS(U, vis, adj)
{
// Mark U as visited
vis[U] = 1;
// Traverse the adjacency list of U
for(var V of adj[U])
{
if (vis[V] == 0)
DFS(V, vis, adj);
}
}
// Function to find the minimum cost
// to color all the vertices of graph
function minCost( N, M, vCost, eCost, sorc, colored, destination)
{
// To store adjacency list
var adj = [];
for(var i = 0; i < N + 1; i++)
adj.push(new Array());
// Loop through the edges to
// create adjacency list
for(var i = 0; i < M; i++)
{
(adj[sorc[i]]).push(destination[i]);
(adj[destination[i]]).push(sorc[i]);
}
// To check if a vertex of the
// graph is visited
var vis = Array(N+1).fill(0);
// Mark visited to all the vertices
// that can be reached by
// colored vertices
for(var i = 0; i < colored.length; i++)
{
// Perform DFS
DFS(colored[i], vis, adj);
}
// To store count of uncolored
// sub-graphs
var X = 0;
// Loop through vertex to count
// uncolored sub-graphs
for(var i = 1; i <= N; i++)
{
// If vertex not visited
if (vis[i] == 0)
{
// Increase count of
// uncolored sub-graphs
X++;
// Perform DFS to mark
// visited to all vertices
// of current sub-graphs
DFS(i, vis, adj);
}
}
// Calculate minimum cost to color
// all vertices
var mincost = X * Math.min(vCost, eCost);
// Print the result
document.write(mincost);
}
// Driver code
// Given number of
// vertices and edges
var N = 3, M = 1;
// Given edges
var sorc = [1];
var destination = [2];
// Given cost of coloring
// and adding an edge
var vCost = 3, eCost = 2;
// Given array of
// colored vertices
var colored = [];
colored.push(1);
minCost(N, M, vCost, eCost,
sorc, colored,
destination);
</script>
Producción:
2
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por veerdwivedi1015 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA