graphs · Problem 1 of 2
Count Connected Components
medium
Amazon
Google
AmazonGooglegraph maps each node to its neighbours. Return how many connected components it has.
countComponents({ "a": ["b"], "b": ["a"], "c": [] }) -> 2Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Running is free — Submit is what records it. Or press ⌘↩
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| countComponents({"a":["b"],"b":["a"],"c":[]}) | two components | 2 | — |
| countComponents({"a":["b"],"b":["a","c"],"c":["b"]}) | one component | 1 | — |
| countComponents({}) | empty graph | 0 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(V + E)
- target space
- O(V)
Every node and edge is examined once. The visited set is what makes that true — without it a cycle never terminates.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left