Dado un gráfico no dirigido que consta de V vértices y una array 2d E[][2] que denota aristas entre pares de Nodes. Dada otra array arr[] que representa los valores asignados a cada Node, la tarea es encontrar el GCD máximo entre los GCD de todos los componentes conectados en el gráfico .
Ejemplos:
Entrada: V = 5, E[][2] = {{1, 3}, {2, 3}, {1, 2}}, arr[] = {23, 43, 123, 54, 2}
Salida: 54
Explicación:
Componente conectado {1, 2, 3}: GCD(arr[1], arr[2], arr[3]) = GCD(23, 43, 123) = 1.
Componente conectado {4}: GCD = 54.
Conectado componente {5}: GCD = 2.
Por lo tanto, el MCD máximo es 54.Entrada: V = 5, E = {{1, 2}, {1, 3}, {4, 5}}, arr[] = { 10, 10, 10, 15, 15 }
Salida: 15
Enfoque: el problema dado se puede resolver realizando un recorrido de búsqueda en profundidad primero en el gráfico dado y luego encontrar el GCD máximo entre todos los componentes conectados. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos maxGCD como INT_MIN , para almacenar el GCD máximo entre todos los componentes conectados .
- Inicialice otra variable, digamos currentGCD como 0 , para almacenar el GCD de cada componente conectado de forma independiente.
- Inicialice una array auxiliar visited[] como falsa para almacenar los Nodes visitados en DFS Traversal .
- Iterar sobre cada vértice sobre el rango [1, V] y realizar los siguientes pasos:
- Si no se visita el vértice actual, es decir, visited[i] = false , entonces inicialice currentGCD como 0 .
- Realice DFS Traversal desde el vértice actual con el valor de currentGCD y actualice el valor de currentGCD como el GCD de currentGCD y arr[i – 1] en cada llamada recursiva .
- Si el valor de currentGCD es mayor que maxGCD , actualice maxGCD como currentGCD .
- Después de completar los pasos anteriores, imprima el valor de maxGCD como resultado.
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;
// Function to find the GCD of two
// numbers a and b
int gcd(int a, int b)
{
// Base Case
if (b == 0)
return a;
// Recursively find the GCD
return gcd(b, a % b);
}
// Function to perform DFS Traversal
void depthFirst(int v, vector<int> graph[],
vector<bool>& visited,
int& currGCD,
vector<int> values)
{
// Mark the visited vertex as true
visited[v] = true;
// Update GCD of current
// connected component
currGCD = gcd(currGCD, values[v - 1]);
// Traverse all adjacent nodes
for (auto child : graph[v]) {
if (visited[child] == false) {
// Recursive call to perform
// DFS traversal
depthFirst(child, graph, visited,
currGCD, values);
}
}
}
// Function to find the maximum GCD
// of nodes among all the connected
// components of an undirected graph
void maximumGcd(int Edges[][2], int E,
int V, vector<int>& arr)
{
vector<int> graph[V + 1];
// Traverse the edges
for (int i = 0; i < E; i++) {
int u = Edges[i][0];
int v = Edges[i][1];
graph[u].push_back(v);
graph[v].push_back(u);
}
// Initialize boolean array
// to mark visited vertices
vector<bool> visited(V + 1, false);
// Stores the maximum GCD value
int maxGCD = INT_MIN;
// Traverse all the vertices
for (int i = 1; i <= V; i++) {
// If node is not visited
if (visited[i] == false) {
// Stores GCD of current
// connected component
int currGCD = 0;
// Perform DFS Traversal
depthFirst(i, graph, visited,
currGCD, arr);
// Update maxGCD
if (currGCD > maxGCD) {
maxGCD = currGCD;
}
}
}
// Print the result
cout << maxGCD;
}
// Driver Code
int main()
{
int E = 3, V = 5;
vector<int> arr = { 23, 43, 123, 54, 2 };
int Edges[][2] = { { 1, 3 }, { 2, 3 }, { 1, 2 } };
maximumGcd(Edges, E, V, arr);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
static int currGCD;
// Function to find the GCD of two
// numbers a and b
static int gcd(int a, int b)
{
// Base Case
if (b == 0)
return a;
// Recursively find the GCD
return gcd(b, a % b);
}
// Function to perform DFS Traversal
static void depthFirst(int v,
ArrayList<Integer> graph[],
boolean visited[], int values[])
{
// Mark the visited vertex as true
visited[v] = true;
// Update GCD of current
// connected component
currGCD = gcd(currGCD, values[v - 1]);
// Traverse all adjacent nodes
for (int child : graph[v]) {
if (visited[child] == false) {
// Recursive call to perform
// DFS traversal
depthFirst(child, graph, visited, values);
}
}
}
// Function to find the maximum GCD
// of nodes among all the connected
// components of an undirected graph
static void maximumGcd(int Edges[][], int E, int V,
int arr[])
{
ArrayList<Integer> graph[] = new ArrayList[V + 1];
// Initialize the graph
for (int i = 0; i < V + 1; i++)
graph[i] = new ArrayList<>();
// Traverse the edges
for (int i = 0; i < E; i++) {
int u = Edges[i][0];
int v = Edges[i][1];
graph[u].add(v);
graph[v].add(u);
}
// Initialize boolean array
// to mark visited vertices
boolean visited[] = new boolean[V + 1];
// Stores the maximum GCD value
int maxGCD = Integer.MIN_VALUE;
// Traverse all the vertices
for (int i = 1; i <= V; i++) {
// If node is not visited
if (visited[i] == false) {
// Stores GCD of current
// connected component
currGCD = 0;
// Perform DFS Traversal
depthFirst(i, graph, visited, arr);
// Update maxGCD
if (currGCD > maxGCD) {
maxGCD = currGCD;
}
}
}
// Print the result
System.out.println(maxGCD);
}
// Driver Code
public static void main(String[] args)
{
int E = 3, V = 5;
int arr[] = { 23, 43, 123, 54, 2 };
int Edges[][] = { { 1, 3 }, { 2, 3 }, { 1, 2 } };
maximumGcd(Edges, E, V, arr);
}
}
// This code is contributed by Kingash.
Python3
# Python 3 program for the above approach from math import gcd import sys # Function to find the GCD of two # numbers a and b currGCD = 0 # Function to perform DFS Traversal def depthFirst(v, graph, visited, values): global currGCD # Mark the visited vertex as true visited[v] = True # Update GCD of current # connected component currGCD = gcd(currGCD, values[v - 1]) # Traverse all adjacent nodes for child in graph[v]: if (visited[child] == False): # Recursive call to perform # DFS traversal depthFirst(child, graph, visited, values) # Function to find the maximum GCD # of nodes among all the connected # components of an undirected graph def maximumGcd(Edges, E, V, arr): global currGCD graph = [[] for i in range(V + 1)] # Traverse the edges for i in range(E): u = Edges[i][0] v = Edges[i][1] graph[u].append(v) graph[v].append(u) # Initialize boolean array # to mark visited vertices visited = [False for i in range(V+1)] # Stores the maximum GCD value maxGCD = -sys.maxsize - 1 # Traverse all the vertices for i in range(1, V + 1, 1): # If node is not visited if (visited[i] == False): # Stores GCD of current # connected component currGCD = 0 # Perform DFS Traversal depthFirst(i, graph, visited, arr) # Update maxGCD if (currGCD > maxGCD): maxGCD = currGCD # Print the result print(maxGCD) # Driver Code if __name__ == '__main__': E = 3 V = 5 arr = [23, 43, 123, 54, 2] Edges = [[1, 3 ], [2, 3], [1, 2]] maximumGcd(Edges, E, V, arr) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
static int currGCD;
// Function to find the GCD of two
// numbers a and b
static int gcd(int a, int b)
{
// Base Case
if (b == 0)
return a;
// Recursively find the GCD
return gcd(b, a % b);
}
// Function to perform DFS Traversal
static void depthFirst(int v, List<List<int>> graph, bool[] visited, int[] values)
{
// Mark the visited vertex as true
visited[v] = true;
// Update GCD of current
// connected component
currGCD = gcd(currGCD, values[v - 1]);
// Traverse all adjacent nodes
foreach(int child in graph[v]) {
if (visited[child] == false) {
// Recursive call to perform
// DFS traversal
depthFirst(child, graph, visited, values);
}
}
}
// Function to find the maximum GCD
// of nodes among all the connected
// components of an undirected graph
static void maximumGcd(int[,] Edges, int E, int V, int[] arr)
{
List<List<int>> graph = new List<List<int>>();
// Initialize the graph
for (int i = 0; i < V + 1; i++)
graph.Add(new List<int>());
// Traverse the edges
for (int i = 0; i < E; i++) {
int u = Edges[i,0];
int v = Edges[i,1];
graph[u].Add(v);
graph[v].Add(u);
}
// Initialize boolean array
// to mark visited vertices
bool[] visited = new bool[V + 1];
// Stores the maximum GCD value
int maxGCD = Int32.MinValue;
// Traverse all the vertices
for (int i = 1; i <= V; i++) {
// If node is not visited
if (visited[i] == false) {
// Stores GCD of current
// connected component
currGCD = 0;
// Perform DFS Traversal
depthFirst(i, graph, visited, arr);
// Update maxGCD
if (currGCD > maxGCD) {
maxGCD = currGCD;
}
}
}
// Print the result
Console.WriteLine(maxGCD);
}
static void Main() {
int E = 3, V = 5;
int[] arr = { 23, 43, 123, 54, 2 };
int[,] Edges = { { 1, 3 }, { 2, 3 }, { 1, 2 } };
maximumGcd(Edges, E, V, arr);
}
}
// This code is contributed by rameshtravel07.
Javascript
<script>
// Javascript program for the above approach
let currGCD;
// Function to find the GCD of two
// numbers a and b
function gcd(a, b)
{
// Base Case
if (b == 0)
return a;
// Recursively find the GCD
return gcd(b, a % b);
}
// Function to perform DFS Traversal
function depthFirst(v, graph, visited, values)
{
// Mark the visited vertex as true
visited[v] = true;
// Update GCD of current
// connected component
currGCD = gcd(currGCD, values[v - 1]);
// Traverse all adjacent nodes
for(let child = 0; child < graph[v].length; child++) {
if (visited[graph[v][child]] == false) {
// Recursive call to perform
// DFS traversal
depthFirst(graph[v][child], graph, visited, values);
}
}
}
// Function to find the maximum GCD
// of nodes among all the connected
// components of an undirected graph
function maximumGcd(Edges, E, V, arr)
{
let graph = [];
// Initialize the graph
for (let i = 0; i < V + 1; i++)
graph.push([]);
// Traverse the edges
for (let i = 0; i < E; i++) {
let u = Edges[i][0];
let v = Edges[i][1];
graph[u].push(v);
graph[v].push(u);
}
// Initialize boolean array
// to mark visited vertices
let visited = new Array(V + 1);
visited.fill(false);
// Stores the maximum GCD value
let maxGCD = Number.MIN_VALUE;
// Traverse all the vertices
for (let i = 1; i <= V; i++) {
// If node is not visited
if (visited[i] == false) {
// Stores GCD of current
// connected component
currGCD = 0;
// Perform DFS Traversal
depthFirst(i, graph, visited, arr);
// Update maxGCD
if (currGCD > maxGCD) {
maxGCD = currGCD;
}
}
}
// Print the result
document.write(maxGCD + "</br>");
}
let E = 3, V = 5;
let arr = [ 23, 43, 123, 54, 2 ];
let Edges = [ [ 1, 3 ], [ 2, 3 ], [ 1, 2 ] ];
maximumGcd(Edges, E, V, arr);
// This code is contributed by decode2207.
</script>
Producción:
54
Complejidad de tiempo: O((V + E) * log(M)), donde M es el elemento más pequeño de la array dada arr[] . Espacio Auxiliar: O(V)
Publicación traducida automáticamente
Artículo escrito por aditya7409 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA