Difference between revisions of "TADM2E 5.17"

From Algorithm Wiki
Jump to: navigation, search
(Created page 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 cycle...")
 
(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...")
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.
-------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().
 
  
 
+
i,e parent[parent[u]] == v,then found cycle of lenght 3
/* 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;
+
    }
+
}
+

Revision as of 05:48, 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.


i,e parent[parent[u]] == v,then found cycle of lenght 3