Thursday 13 November 2014

Detecting Cycle in undirected Graph or Check if the given graph is tree.

We can use DFS to detect cycle in an undirected graph in O(V+E) time. We do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle. 

Assumption ::There are no parallel edges between any two vertices.




public void solve(int testNumber, EvenTreeInputReader in, PrintWriter out) {
        //Read inputs and write the main function.
        int v = in.nextInt();
        int e = in.nextInt();
        ArrayList<Integer>[] alist = new ArrayList[v];
        for(int i=0;i<v;i++) alist[i] = new ArrayList<Integer>();
        while(e-->0) {
            int n1 = in.nextInt();
            int n2 = in.nextInt();
            alist[n1-1].add(n2-1);
            alist[n2-1].add(n1-1);
        }

        boolean[] visited = new boolean[v];
        int[] parent = {-1};
        boolean[] isTree = {true};
        if(isTreeUtil(v,alist,visited,parent)){
            System.out.println("YES");
        }
        else System.out.println("NO");
    }

    public boolean isTreeUtil(int v,ArrayList<Integer>[] alist, boolean[] visited,int[] parent) {

        for(int i=0;i<v;i++) {
            if(!visited[i]) {
               if(!isTree(i, alist, visited, parent)) return false;
            }
        }
        return true;
    }

    public boolean isTree(int v,ArrayList<Integer>[] alist,boolean[] visited,int[] parent) {

        visited[v] = true;

        for(int i=0;i<alist[v].size();i++) {
            int n = alist[v].get(i);
            if(!visited[n]) {
                parent[0] = v;
                if(!isTree(n,alist,visited,parent)) return false;
            }
            else {
                if(n != parent[0]) return false;
            }
        }
        return true;
    }

No comments:

Post a Comment