Data Modelling & AI Data Structure & Algorithm

Maximum GCD of all nodes in a connected component of an Undirected Graph

23 June 2025

1

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

Output:

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!

1 COMMENT

clairsentient 7 May 2026 At 10:28 am

… [Trackback]

[…] Read More here on that Topic: geeksforgeeks.org/maximum-gcd-of-all-nodes-in-a-connected-component-of-an-undirected-graph/ […]

Log in to leave a comment

Maximum GCD of all nodes in a connected component of an Undirected Graph

C++

Java

Python3

C#

Javascript

Adding Persistent Memory to Claude Code with the Lightweight memsearch Plugin

GLM-5 vs. MiniMax M2.5 vs. Gemini 3 Deep Think: Which Model Fits Your AI Agent Stack?

We Extracted OpenClaw’s Memory System and Open-Sourced It (memsearch)

1 COMMENT

LEAVE A REPLY Cancel reply

Most Popular

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

Samsung’s June update brings Galaxy S25 three powerful AI tricks the S26 already had

Your Galaxy S25 just picked up three more Galaxy AI features

No one can agree on these phones. [Video]

EDITOR PICKS

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

Samsung’s June update brings Galaxy S25 three powerful AI tricks the S26 already had

Your Galaxy S25 just picked up three more Galaxy AI features

POPULAR POSTS

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

Samsung’s June update brings Galaxy S25 three powerful AI tricks the S26 already had

Your Galaxy S25 just picked up three more Galaxy AI features

POPULAR CATEGORY

ABOUT US

FOLLOW US