Dado un grafo ponderado no dirigido G que consiste en N vértices y M aristas, y dos arreglos Aristas[][2] y Peso[] que consisten en M aristas del gráfico y pesos de cada arista respectivamente, la tarea es encontrar el producto máximo de dos cualesquiera vértices del componente conexo más grande del gráfico , formado al conectar todos los bordes con el mismo peso .
Ejemplos:
Entrada: N = 4, Bordes[][] = {{1, 2}, {1, 2}, {2, 3}, {2, 3}, {2, 4}}, Peso[] = {1 , 2, 1, 3, 3}
Salida: 12
Explicación:
- Componentes de aristas de peso 1, 1 ↔ 2 ↔ 3. El producto máximo de dos vértices cualesquiera de este componente es 6.
- Componentes de aristas de peso 2, 1 ↔ 2. El producto máximo de dos vértices cualesquiera de esta componente es 2.
- Componentes de aristas de peso 3, 4 ↔ 2 ↔ 3. El producto máximo de dos vértices cualesquiera de esta componente es 12.
Por lo tanto, el producto máximo entre todos los componentes conectados de tamaño 3 (que es el máximo) es 12.
Entrada: N = 5, Bordes[][] = {{1, 5}, {2, 5}, {3, 5}, {4, 5}, {1, 2}, {2, 3}, { 3, 4}}, Peso[] = {1, 1, 1, 1, 2, 2, 2}
Salida: 20
Enfoque: el problema dado se puede resolver realizando el recorrido DFS en el gráfico dado y maximizando el producto del primer y segundo Node máximo para todos los componentes conectados del mismo peso. Siga los pasos a continuación para resolver el problema:
- Almacene todos los bordes correspondientes a todos los pesos únicos en un mapa M .
- Inicialice una variable, digamos res como 0 para almacenar el producto máximo de dos Nodes cualquiera de los componentes conectados de los mismos pesos.
- Recorra el mapa y para cada clave como peso cree un gráfico conectando todos los bordes mapeados con el peso particular y realice las siguientes operaciones:
- Encuentre el valor del valor del Node máximo (digamos M1 ) y el segundo máximo (digamos M2 ) y el tamaño de todos los componentes conectados del gráfico realizando el DFS Traversal en el gráfico creado.
- Actualice el valor de res al máximo de res , M1 y M2 si el tamaño de los componentes conectados actualmente es al menos el componente conectado de mayor tamaño encontrado anteriormente.
- Después de completar los pasos anteriores, imprima el valor de res como el producto máximo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the first and second largest
// element in a connected component
int Max, sMax;
// Stores the count of nodes
// in the connected components
int cnt = 0;
// Function to perform DFS Traversal
// on a given graph and find the first
// and the second largest elements
void dfs(int u, int N, vector<bool>& vis,
vector<vector<int> >& adj)
{
// Update the maximum value
if (u > Max) {
sMax = Max;
Max = u;
}
// Update the second max value
else if (u > sMax) {
sMax = u;
}
// Increment size of component
cnt++;
// Mark current node visited
vis[u] = true;
// Traverse the adjacent nodes
for (auto to : adj[u]) {
// If to is not already visited
if (!vis[to]) {
dfs(to, N, vis, adj);
}
}
return;
}
// Function to find the maximum
// product of a connected component
int MaximumProduct(
int N, vector<pair<int, int> > Edge,
vector<int> wt)
{
// Stores the count of edges
int M = wt.size();
// Stores all the edges mapped
// with a particular weight
unordered_map<int,
vector<pair<int, int> > >
mp;
// Update the map mp
for (int i = 0; i < M; i++)
mp[wt[i]].push_back(Edge[i]);
// Stores the result
int res = 0;
// Traverse the map mp
for (auto i : mp) {
// Stores the adjacency list
vector<vector<int> > adj(N + 1);
// Stores the edges of
// a particular weight
vector<pair<int, int> > v = i.second;
// Traverse the vector v
for (int j = 0; j < v.size(); j++) {
int U = v[j].first;
int V = v[j].second;
// Add an edge
adj[U].push_back(V);
adj[V].push_back(U);
}
// Stores if a vertex
// is visited or not
vector<bool> vis(N + 1, 0);
// Stores the maximum
// size of a component
int cntMax = 0;
// Iterate over the range [1, N]
for (int u = 1; u <= N; u++) {
// Assign Max, sMax, count = 0
Max = sMax = cnt = 0;
// If vertex u is not visited
if (!vis[u]) {
dfs(u, N, vis, adj);
// If cnt is greater
// than cntMax
if (cnt > cntMax) {
// Update the res
res = Max * sMax;
cntMax = cnt;
}
// If already largest
// connected component
else if (cnt == cntMax) {
// Update res
res = max(res, Max * sMax);
}
}
}
}
// Return res
return res;
}
// Driver Code
int main()
{
int N = 5;
vector<pair<int, int> > Edges
= { { 1, 2 }, { 2, 5 }, { 3, 5 }, { 4, 5 }, { 1, 2 }, { 2, 3 }, { 3, 4 } };
vector<int> Weight = { 1, 1, 1, 1,
2, 2, 2 };
cout << MaximumProduct(N, Edges, Weight);
return 0;
}
20
Complejidad de Tiempo: O(N 2 * log N + M)
Espacio Auxiliar: O(N 2 )