TADM2E 5.17

From Algorithm Wiki
Revision as of 15:39, 30 April 2016 by NotQuantum (Talk | contribs)

Jump to: navigation, search

(b) use DFS to find cycle of length 3.

we maintain an array parent[i].

while processing any backedge u-v we check whether grandparent of u is equal to v .if true we found a cycle of length 3. grandparentU = parent[parent[u]]

i,e grandparentU == v,then found cycle of length 3.stop futher exploration of DFS