Number of Connected Components in an Undirected Graph
Goldman Sachs
MicrosoftThe problem
You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph. Return the number of connected components in the graph.
Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2 Explanation:
- Nodes {0,1,2} form one connected component.
- Nodes {3,4} form another connected component.
- Total number of connected components = 2.
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] Output: 1 Explanation:
- All nodes {0,1,2,3,4} are connected, forming a single connected component.
- Total number of connected components = 1.
Input: n = 5, edges = [[0,1]]
- 1 <= n <= 2000
- 1 <= edges.length <= 5000
- edges[i].length == 2
- 0 <= ai <= bi < n
- ai != bi
- There are no repeated edges.
cpp
class Solution {
public:
int countComponents(int n, vector<vector<int>>& edges) {
// Your code goes here
}
};java
class Solution {
public int countComponents(int n, int[][] edges) {
// Your code goes here
}
}python
class Solution(object):
def countComponents(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: int
"""
# Your code goes herejavascript
/**
* @param {number} n
* @param {number[][]} edges
* @return {number}
*/
var countComponents = function(n, edges) {
// Your code goes here
};csharp
public class Solution
{
public int CountComponents(int n, List<int[]> edges)
{
// Your code goes here
}
}go
func countComponents(n int, edges [][]int) int {
// Your code goes here
}Stuck? Show a way to structure it+
- 01Build adjacency from edges.
- 02Keep a visited set or DSU parent array.
- 03Start a traversal at each unvisited node.
- 04Increment the component count per start.
- 05Return the count.
Reference answer
Then expect these follow-ups
How would directed weak components differ?
Tests: graph definitions
When is DSU preferable?
Tests: tradeoffs
Hiring now
Get the Goldman Sachs interview, not just the prep
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Next question