# Difference between revisions of "TADM2E 5.17"

From Algorithm Wiki

Rahul Biswas (Talk | contribs) (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...") |
Rahul Biswas (Talk | contribs) |
||

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 | + |

## 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