Количество узлов с максимальным соединением в неориентированном графе

Дан неориентированный граф с N узлами и E ребрами, за которыми следуют E реберных соединений. Задача состоит в том, чтобы найти количество узлов с максимальным количеством соединений.

Примеры:

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

Подход . Задача может быть решена путем сохранения количества связанных узлов для каждого узла внутри вектора. А затем найдите максимальное количество подключенных узлов к любому из узлов и получите его количество .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N)
Вспомогательное пространство : O(N)