Count of nodes with maximum connection in an undirected graph

Namachila November 19, 2025

0 0 5 minutes read

Given an undirected graph with N nodes and E edges, followed by E edge connections. The task is to find the count of nodes with maximum connections

Examples:

Input: N =10, E =13,
edges[][] = { {1, 4}, {2, 3}, {4, 5}, {3, 9}, {6, 9}, {3, 8}, {10, 4},
{2, 7}, {3, 6}, {2, 8}, {9, 2}, {1, 10}, {9, 10} }
Output: 3
Explanation: The connections for each of the nodes are show below:

1 -> 4, 10

2 -> 3, 7, 8, 9

3 -> 2, 9, 8, 6

4 -> 1, 5, 10

5 -> 4

6 -> 9, 3

7 -> 2

8 -> 3, 2

9 -> 3, 6, 2, 10

10 -> 4, 9, 1

Therefore, number of nodes with maximum connections are 3 viz. {2, 3, 9}

Input: N = 8, E = 7,
edges[][] = { {0, 2}, {1, 5}, {2, 3}, {5, 7}, {2, 4}, {5, 6}, {1, 2} }
Output: 3

Approach: The task can be solved by storing the number of connected nodes for every node inside a vector. And then, find the maximum connected nodes to any of the nodes & get its count.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of nodes
// with maximum connections
void get(map<int, vector<int> > graph)
{
    // Stores the number of connections
    // of each node
    vector<int> v;
 
    // Stores the maximum connections
    int mx = -1;
    for (int i = 0; i < graph.size(); i++) {
        v.push_back(graph[i].size());
        mx = max(mx, (int)graph[i].size());
    }
 
    // Resultant count
    int cnt = 0;
    for (auto i : v) {
        if (i == mx)
            cnt++;
    }
 
    cout << cnt << endl;
}
 
// Drive Code
int main()
{
    map<int, vector<int> > graph;
    int nodes = 10, edges = 13;
 
    // 1
    graph[1].push_back(4);
    graph[4].push_back(1);
 
    // 2
    graph[2].push_back(3);
    graph[3].push_back(2);
 
    // 3
    graph[4].push_back(5);
    graph[5].push_back(4);
 
    // 4
    graph[3].push_back(9);
    graph[9].push_back(3);
 
    // 5
    graph[6].push_back(9);
    graph[9].push_back(6);
 
    // 6
    graph[3].push_back(8);
    graph[8].push_back(3);
 
    // 7
    graph[10].push_back(4);
    graph[4].push_back(10);
 
    // 8
    graph[2].push_back(7);
    graph[7].push_back(2);
 
    // 9
    graph[3].push_back(6);
    graph[6].push_back(3);
 
    // 10
    graph[2].push_back(8);
    graph[8].push_back(2);
 
    // 11
    graph[9].push_back(2);
    graph[2].push_back(9);
 
    // 12
    graph[1].push_back(10);
    graph[10].push_back(1);
 
    // 13
    graph[9].push_back(10);
    graph[10].push_back(9);
 
    get(graph);
    return 0;
}

Java

// Java program for the above approach
import java.util.ArrayList;
import java.util.HashMap;
 
class GFG {
 
  // Function to count the number of nodes
  // with maximum connections
  static void get(HashMap<Integer, ArrayList<Integer>> graph)
  {
     
    // Stores the number of connections
    // of each node
    ArrayList<Integer> v = new ArrayList<Integer>();
 
    // Stores the maximum connections
    int mx = -1;
    for (int i = 0; i < graph.size(); i++) {
      v.add(graph.get(i).size());
      mx = Math.max(mx, (int) graph.get(i).size());
    }
 
    // Resultant count
    int cnt = 0;
    for (int i : v) {
      if (i == mx)
        cnt++;
    }
 
    System.out.println(cnt);
  }
 
  // Drive Code
  public static void main(String args[]) {
 
    HashMap<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>();
    int nodes = 10, edges = 13;
 
    for (int i = 0; i <= nodes; i++) {
      graph.put(i, new ArrayList<>());
    }
    // 1
    graph.get(1).add(4);
    graph.get(4).add(1);
 
    // 2
    graph.get(2).add(3);
    graph.get(3).add(2);
 
    // 3
    graph.get(4).add(5);
    graph.get(5).add(4);
 
    // 4
    graph.get(3).add(9);
    graph.get(9).add(3);
 
    // 5
    graph.get(6).add(9);
    graph.get(9).add(6);
 
    // 6
    graph.get(3).add(8);
    graph.get(8).add(3);
 
    // 7
    graph.get(10).add(4);
    graph.get(4).add(10);
 
    // 8
    graph.get(2).add(7);
    graph.get(7).add(2);
 
    // 9
    graph.get(3).add(6);
    graph.get(6).add(3);
 
    // 10
    graph.get(2).add(8);
    graph.get(8).add(2);
 
    // 11
    graph.get(9).add(2);
    graph.get(2).add(9);
 
    // 12
    graph.get(1).add(10);
    graph.get(10).add(1);
 
    // 13
    graph.get(9).add(10);
    graph.get(10).add(9);
 
    get(graph);
  }
}
 
// This code is contributed by saurabh_jaiswal.

Python3

# Python code for the above approach
 
# Function to count the number of nodes
# with maximum connections
def get(graph):
 
    # Stores the number of connections
    # of each node
    v = [];
 
    # Stores the maximum connections
    mx = -1;
    for arr in graph.values():
        v.append(len(arr));
        mx = max(mx, (len(arr)));
     
    # Resultant count
    cnt = 0;
    for i in v:
        if (i == mx):
            cnt += 1
     
    print(cnt)
 
# Drive Code
graph = {}
 
nodes = 10
edges = 13;
for i in range(1, nodes + 1):
    graph[i] = []
 
# 1
graph[1].append(4);
graph[4].append(1);
 
# 2
graph[2].append(3);
graph[3].append(2);
 
# 3
graph[4].append(5);
graph[5].append(4);
 
# 4
graph[3].append(9);
graph[9].append(3);
 
# 5
graph[6].append(9);
graph[9].append(6);
 
# 6
graph[3].append(8);
graph[8].append(3);
 
# 7
graph[10].append(4);
graph[4].append(10);
 
# 8
graph[2].append(7);
graph[7].append(2);
 
# 9
graph[3].append(6);
graph[6].append(3);
 
# 10
graph[2].append(8);
graph[8].append(2);
 
# 11
graph[9].append(2);
graph[2].append(9);
 
# 12
graph[1].append(10);
graph[10].append(1);
 
# 13
graph[9].append(10);
graph[10].append(9);
 
get(graph);
 
# This code is contributed by Saurabh Jaiswal

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG {
 
  // Function to count the number of nodes
  // with maximum connections
  static void get(Dictionary<int, List<int>> graph)
  {
 
    // Stores the number of connections
    // of each node
    List<int> v = new List<int>();
 
    // Stores the maximum connections
    int mx = -1;
    for (int i = 0; i < graph.Count; i++) {
      v.Add(graph[i].Count);
      mx = Math.Max(mx, (int) graph[i].Count);
    }
 
    // Resultant count
    int cnt = 0;
    foreach (int i in v) {
      if (i == mx)
        cnt++;
    }
 
    Console.WriteLine(cnt);
  }
 
  // Drive Code
  public static void Main(String []args) {
 
    Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
    int nodes = 10;
 
    for (int i = 0; i <= nodes; i++) {
      graph.Add(i, new List<int>());
    }
    // 1
    graph[1].Add(4);
    graph[4].Add(1);
 
    // 2
    graph[2].Add(3);
    graph[3].Add(2);
 
    // 3
    graph[4].Add(5);
    graph[5].Add(4);
 
    // 4
    graph[3].Add(9);
    graph[9].Add(3);
 
    // 5
    graph[6].Add(9);
    graph[9].Add(6);
 
    // 6
    graph[3].Add(8);
    graph[8].Add(3);
 
    // 7
    graph[10].Add(4);
    graph[4].Add(10);
 
    // 8
    graph[2].Add(7);
    graph[7].Add(2);
 
    // 9
    graph[3].Add(6);
    graph[6].Add(3);
 
    // 10
    graph[2].Add(8);
    graph[8].Add(2);
 
    // 11
    graph[9].Add(2);
    graph[2].Add(9);
 
    // 12
    graph[1].Add(10);
    graph[10].Add(1);
 
    // 13
    graph[9].Add(10);
    graph[10].Add(9);
 
    get(graph);
  }
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
       // JavaScript code for the above approach
 
       // Function to count the number of nodes
       // with maximum connections
       function get(graph)
       {
        
           // Stores the number of connections
           // of each node
           let v = [];
 
           // Stores the maximum connections
           let mx = -1;
           for (let [key, arr] of graph) {
               v.push(arr.length);
               mx = Math.max(mx, (arr.length));
           }
 
           // Resultant count
           let cnt = 0;
           for (let i of v) {
               if (i == mx)
                   cnt++;
           }
 
           document.write(cnt + "<br>")
       }
 
       // Drive Code
 
       let graph = new Map();
 
 
       let nodes = 10, edges = 13;
       for (let i = 1; i <= nodes; i++) {
           graph.set(i, []);
       }
       // 1
       graph.get(1).push(4);
       graph.get(4).push(1);
 
       // 2
       graph.get(2).push(3);
       graph.get(3).push(2);
 
       // 3
       graph.get(4).push(5);
       graph.get(5).push(4);
 
       // 4
       graph.get(3).push(9);
       graph.get(9).push(3);
 
       // 5
       graph.get(6).push(9);
       graph.get(9).push(6);
 
       // 6
       graph.get(3).push(8);
       graph.get(8).push(3);
 
       // 7
       graph.get(10).push(4);
       graph.get(4).push(10);
 
       // 8
       graph.get(2).push(7);
       graph.get(7).push(2);
 
       // 9
       graph.get(3).push(6);
       graph.get(6).push(3);
 
       // 10
       graph.get(2).push(8);
       graph.get(8).push(2);
 
       // 11
       graph.get(9).push(2);
       graph.get(2).push(9);
 
       // 12
       graph.get(1).push(10);
       graph.get(10).push(1);
 
       // 13
       graph.get(9).push(10);
       graph.get(10).push(9);
 
       get(graph);
 
      // This code is contributed by Potta Lokesh
   </script>

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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