Connected Components (cont)
Consider maintenance of such a graph representation:
- initially,
(nC == nV) (because no edges)
- adding an edge may reduce
nC
- removing an edge may increase
nC
-
cc[] can simplify path checking
(ensure v,w are in same component before starting search)
Additional maintenance cost amortised by much reduced cost
for nComponents() and sameComponent()
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}