(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

for(int i=0;i < edges;i++){
int u = in.nextInt();
int v = in.nextInt();

}

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

}

public static void dfs(Integer u){
//processVertexEarly(node);

disc[u] = true;

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;
}


}