Difference between revisions of "TADM2E 5.17"

From Algorithm Wiki
Jump to: navigation, search
(Replaced content with "use dfs to find cycle of lenght 3. we maintain an array parent[i]. while processing any backedge u-v we check whether gradparent of u is equal to v .if true we found a c...")
Line 4: Line 4:
  
 
while processing any backedge u-v we check whether gradparent of u is equal to v .if true we found a cycle of lenght 3.
 
while processing any backedge u-v we check whether gradparent of u is equal to v .if true we found a cycle of lenght 3.
 +
gradparentU = parent[parent[u]]
  
 
+
i,e  gradparentU == v,then found cycle of lenght 3.stop futher exploration of dfs
i,e  parent[parent[u]] == v,then found cycle of lenght 3
+

Revision as of 05:49, 31 January 2016

use dfs to find cycle of lenght 3.

we maintain an array parent[i].

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

i,e gradparentU == v,then found cycle of lenght 3.stop futher exploration of dfs