Solution: Count the Number of Edges in an Undirected Graph

Let’s solve the Count the Number of Edges in an Undirected Graph problem.

We'll cover the following

Statement

Given an n number of nodes in an undirected graph, compute the total number of bidirectional edges.

Constraints:

  • 0≤0 \leqn≤102 \leq 10^2

  • 0≤0 \leqedges.length ≤n(n−1)/2\leq n(n-1)/2

  • edges[i].length ==2== 2

  • 1≤x,y≤1 \leq x,y \leqn

  • x≠yx\neq y

  • There are no multiple edges between any two vertices

  • There are no self-loops

Solution

This approach iterates over each vertex in the graph and calculates the sum of the lengths of adjacency lists corresponding to each vertex. The idea is to count the number of connections or edges in the graph. Dividing the final sum by 22 ensures that each edge is counted only once because, in an undirected graph, each edge is represented twice (once for each vertex it connects). Therefore, dividing by 22 gives the actual count of edges in the graph. This method effectively traverses the adjacency list representation of the graph to determine the total number of edges.

Let’s look at the illustration below to better understand the solution:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.