Given a list of nodes in a doubly linked list. All nodes that are neighbor in the original doubly linked list forms a strong component. Given only the list of nodes, what's the number of strong component?
Example:
The underlying doubly linked list looks like: 1 <-> 2 <-> 4 <-> 7 <-> 9 <-> 11, but this are not given as the input.
The input is a list of nodes: 1, 2, 7, 9, 11. There should be 2 strong component. {1, 2}, {7, 9, 11}
Analysis
The idea is to first add all nodes in the list into a set. Then start from one node, and remove the node and all connected nodes from the set.
Compleixty
Time: O(N)
Space: O(N)
Read full article from List Strong Component
No comments:
Post a Comment