Difference between revisions of "TADM2E 5.17"
From Algorithm Wiki
Rahul Biswas (talk | contribs) |
NotQuantum (talk | contribs) m (Fixed spelling) |
||
| Line 1: | Line 1: | ||
| − | (b) use | + | (b) use DFS to find cycle of length 3. |
we maintain an array parent[i]. | we maintain an array parent[i]. | ||
| − | while processing any backedge u-v we check whether | + | 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 | + | i,e grandparentU == v,then found cycle of length 3.stop futher exploration of DFS |
Revision as of 15:39, 30 April 2016
(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
