## Sunday, July 30, 2017

### List Strong Component

http://wxx5433.github.io/list-strong-component.html#
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.
```  public int getNumStrongComponent(DoublyLinkedListNode[] nodes) {
int numStrongComponents = 0;
for (DoublyLinkedListNode node : nodes) {
}
while (!set.isEmpty()) {
set.remove(node);
while (set.contains(cur)) {
set.remove(cur);
cur = cur.next;
}
cur = node.prev;
while (set.contains(cur)) {
set.remove(cur);
cur = cur.prev;
}
numStrongComponents++;
}
return numStrongComponents;
}
```

https://www.careercup.com/question?id=18880663