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>
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