TADM2E 5.17

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.

---

1

| / \ | / \ | 2 3 | / \ | / \ -4 5

Here u=4 to v=1 has backedge and grandparent of u=4 is 1,so condition satifies parent[parent[u]] == v hence given graph has cycle of lenght 3.we stop here to futher explore dfs().

/* java program

* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/

package pkg5.pkg9;

import java.util.ArrayList; import java.util.Scanner; import static pkg5.pkg9.TwoColor.nodes;

/**

*
* @author Rahul
*/

public class Test5_17 {

   /**
    * @param args the command line arguments
    */
   static  ArrayList<ArrayList<Integer>> graph ;
   static int nodes;
   static int edges;
   static boolean[] disc;
   static boolean[] processed;
   static Integer[] parent;
   static boolean found3_LenCycle = false;
   public static void main(String[] args) {
       // TODO code application logic here
       
       Scanner in = new Scanner(System.in);
      
       nodes = in.nextInt();
       edges = in.nextInt();
       
       disc = new boolean[nodes];
       processed = new boolean[nodes];
       parent = new Integer[nodes];
      
      
       graph = new ArrayList<ArrayList<Integer>>(nodes);
       for(int i=0;i < nodes;i++)
           graph.add(i,new ArrayList<Integer>());
      
       for(int i=0;i < edges;i++){
           int u = in.nextInt();
           int v = in.nextInt();
           
           graph.get(u).add(v);
           graph.get(v).add(u);
       }
       
       for(int i=0;i < nodes;i++){
           if( !disc[i]){
               parent[i] = null;
               dfs(i);
           }
               
       }
       
       if(found3_LenCycle)
           System.out.println("found 3-length cycle");
       else
           System.out.println("not found 3-length cycle");
       
   }
   
   public static void dfs(Integer u){
       //processVertexEarly(node);
       ArrayList<Integer> adjList = graph.get(u);
       
       disc[u] = true;
       
       for(Integer v : adjList){
           if( !disc[v]){//tree edge
               parent[v]= u;
              // processEdge(u,v);
               dfs(v);
           }else if(!processed[v]){ //back edge
               processEdge(u,v);
           }
           
           if(found3_LenCycle)
               break;
       }
       
       processed[u] = true;
   }
   
   public static void processEdge(Integer u,Integer v){
       
       if(parent[parent[u]] != null && parent[parent[u]]==v )
           found3_LenCycle = true;
   }

}