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

Retrieved from "https://algorist.com/algowiki_v2/index.php?title=TADM2E_5.17&oldid=386"