Difference between revisions of "TADM2E 5.17"
From Algorithm Wiki
Rahul Biswas (talk | contribs) |
Rahul Biswas (talk | contribs) |
||
| Line 1: | Line 1: | ||
| − | use dfs to find cycle of lenght 3. | + | (b) use dfs to find cycle of lenght 3. |
we maintain an array parent[i]. | we maintain an array parent[i]. | ||
Revision as of 05:53, 31 January 2016
(b) 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
