Given an undirected graph consisting of V vertices and a 2d array E[][2] denoting edges between pairs of nodes. Given another array arr[] representing values assigned to each node, the task is to find the maximum GCD among the GCD of all connected components in the graph.
Examples:
Input: V = 5, E[][2] = {{1, 3}, {2, 3}, {1, 2}}, arr[] = {23, 43, 123, 54, 2}
Output: 54
Explanation:
Connected component {1, 2, 3}: GCD(arr[1], arr[2], arr[3]) = GCD(23, 43, 123) = 1.
Connected component {4}: GCD = 54.
Connected component {5}: GCD = 2.
Therefore, the maximum GCD is 54.Input: V = 5, E = {{1, 2}, {1, 3}, {4, 5}}, arr[] = { 10, 10, 10, 15, 15 }
Output: 15
Approach: The given problem can be solved by performing Depth First Search traversal on the given graph and then find the maximum GCD among all the connected components. Follow the steps below to solve the problem:
- Initialize a variable, say maxGCD as INT_MIN, to store the maximum GCD among all the connected components.
- Initialize another variable, say currentGCD as 0, to store the GCD of each connected component independently.
- Initialize an auxiliary array visited[] as false to store the visited nodes in the DFS Traversal.
- Iterate over each vertex over the range [1, V] and perform the following steps:
- If the current vertex is not visited, i.e. visited[i] = false, then initialize currentGCD as 0.
- Perform DFS Traversal from the current vertex with the currentGCD value and update currentGCD value as the GCD of currentGCD and arr[i – 1] in each recursive call.
- If the value of currentGCD is greater than maxGCD, then update maxGCD as currentGCD.
- After completing the above steps, print the value of maxGCD as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the GCD of two// numbers a and bint 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 Traversalvoid 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 graphvoid 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 Codeint 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 approachimport 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 approachfrom math import gcdimport sys# Function to find the GCD of two# numbers a and bcurrGCD = 0# Function to perform DFS Traversaldef 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 graphdef 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 Codeif __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 approachusing 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> |
Output:
54
Time Complexity: O((V + E) * log(M)), where M is the smallest element of the given array arr[].
Auxiliary Space: O(V)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
