{"id":1877,"date":"2020-07-01T09:46:46","date_gmt":"2020-07-01T09:46:46","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1877"},"modified":"2022-03-28T01:31:05","modified_gmt":"2022-03-28T01:31:05","slug":"detect-cycle","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/detect-cycle\/","title":{"rendered":"Detect Cycle"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Breadth First Search, Disjoint Set<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given an undirected graph, print Yes if a cycle is present in the graph else print No.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

Cycle in a graph means there’s a loop in between its edges.
\nIf we traverse a graph and after visited certain vertices we reach the vertex from where we have started, then the graph is said to have a cycle or a loop.<\/p>\n

For every visited vertex v<\/code>, when we have found any adjacent vertex u<\/code>, such that u<\/code> is already visited, and u<\/code> is not the parent of vertex v<\/code>. Then one cycle is detected.
\nThis problem can be solved by many ways like Breadth First Search<\/strong>, Depth First Search<\/strong> or Disjoint Set<\/strong>.<\/p>\n<\/blockquote>\n

Method 1 (Using BFS) :<\/h4>\n
\n

In this method we are going to use Breadth First Search<\/strong> or BFS<\/strong> to find cycle in a graph. In dfs for each vertex v<\/code> we iterate through all its adjacent vertices and for each vertex a<\/code> and mark it visited, further make v<\/code> the parent of a<\/code> (so that parent is not considered for cycle).<\/p>\n

If there is any vertex a<\/code> which is already visited earlier, then we check if it is the parent of a<\/code> or not. If not, then there exist a cycle.<\/p>\n<\/blockquote>\n

Method 2 (Using Disjoint Set) :<\/h4>\n
\n

Disjoint Set Union<\/strong> or DSU<\/strong> data structure is also sometimes called Union-Find Set<\/strong>. This data structure is used to keep track of the different disjoint sets.
\nIt basically performs two operations :<\/p>\n

    \n
  1. Union :<\/strong> It takes two vertices and join them in a single set (if it is not already there).<\/li>\n
  2. Find :<\/strong> Determines in which subset the element is.<\/li>\n<\/ol>\n

    We will use a parent[]<\/code> array to keep track of the parents of each vertex. ith<\/code> element will store the root\/parent of ith<\/code> vertex. Now for every edge (uv) , check if the root of u<\/code> and v<\/code> is same using find()<\/strong>, if the root is same then there exist a cycle. If not, perform union()<\/strong> with both vertices to update the parent[]<\/code> array. <\/p>\n

    How is the above approach actually working?
    \nEach disjoint set stores the vertices which are connected (directly or indirectly) to each other and has no relation\/connection with any other vertex (as it is non overlapping set), so if there is any pair of vertices (edge) which belongs to the same set this will create a cycle in the graph as they belong to the same root vertex and they are also connected with each other.<\/p>\n<\/blockquote>\n

    \"\"<\/p>\n

    Algorithms :<\/h3>\n
    \n

    union()<\/strong> :<\/p>\n

      \n
    1. For two vertices u<\/code> & v<\/code>, find the root for both vertices using find()<\/strong> (a=find(u)<\/code> & b = find(v)<\/code>).<\/li>\n
    2. If the root of u<\/code> & v<\/code> are not similar, check the level of a<\/code> & b<\/code> as follows:\n
        \n
      • if (level[a]>* else if (<\/code>level[a]>level[b]), update <\/code>parent[b] = a`.<\/li>\n
      • else , update parent[b]=a<\/code> & update level[a] = level[a]+1<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ol>\n

        find()<\/strong> : <\/p>\n

          \n
        1. If (parent[v]==v)<\/code>, returns the vertex v<\/code> (which is root).<\/li>\n
        2. Else, update parent[v]<\/code> by recursively looking up the tree for the root. (find(parent[v]))<\/code>.<\/li>\n<\/ol>\n<\/blockquote>\n

          Complexity Analysis:<\/h3>\n
          \n

          The time complexity<\/strong> of Breadth First Search<\/strong> is represented in the form of O(V + E)<\/code>, where V<\/code> is the number of nodes and E<\/code> is the number of edges.<\/p>\n

          The space complexity<\/strong> of the algorithm is O(V)<\/code> as it requires two arrays ( visited[ ] & parent[ ]) of size V<\/code>.<\/p>\n

          Talking about Union-Find<\/strong> data structure, since we have used path compression & union by level (refer to Disjoint Set<\/strong> article for more detailed explanation), we will reach nearly constant time O(1)<\/code> for each query. It turns out, that the final amortized time complexity is O(\u03b1(V))<\/code>, where \u03b1(V)<\/code> is the inverse Ackermann function, which grows very slowly (\u03b1(V)<5)<\/code>. In our case a single call might take O(logn)<\/code> in the worst case, but if we do m such calls back to back we will end up with an average time of O(\u03b1(n))<\/code>.<\/p>\n<\/blockquote>\n

          Solutions:<\/h3>\n

          \t\t\t\t\t\t