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.
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