title: Union-Find algorithm and determining whether an edge belongs to a cycle in a graph
body: <p>I'm reading a book about algorithms ("Data Structures and Algorithms in C++") and have come across the following exercise:</p>
  
  <blockquote>
    <p>Ex. 20. Modify <code>cycleDetectionDFS()</code> so that it could determine whether a particular edge is part of a cycle in an undirected graph.</p>
  </blockquote>
  
  <p>In the chapter about graphs, the book reads:</p>
  
  <blockquote>
    <p>Let us recall from a preceding section that depth-first search
    guaranteed generating a spanning tree in which no elements of <code>edges</code>
    used by <code>depthFirstSearch()</code> led to a cycle with other element of <code>edges</code>.
    This was due to the fact that if vertices <em>v</em> and <em>u</em> belonged to <code>edges</code>,
    then the <em>edge(vu)</em> was disregarded by <code>depthFirstSearch()</code>. A problem
    arises when <code>depthFirstSearch()</code> is modified so that it can detect
    whether a specific <em>edge(vu)</em> is part of a cycle (see Exercise 20).
    Should such a modified depth-first search be applied to each edge
    separately, then the total run would be O(E(E+V)), which could turn
    into O(V^4) for dense graphs. Hence, a better method needs to be
    found.</p>
    
    <p>The task is to determine if two vertices are in the same set. Two
    operations are needed to implement this task: finding the set to which
    a vertex <em>v</em> belongs and uniting two sets into one if vertex <em>v</em> belongs
    to one of them and <em>w</em> to another. This is known as the <em>union-find
    problem</em>.</p>
  </blockquote>
  
  <p>Later on, author describes how to merge two sets into one in case an edge passed to the function <code>union(edge e)</code> connects vertices in distinct sets.</p>
  
  <p>However, still I don't know how to quickly check whether an edge is part of a cycle. Could someone give me a rough explanation of such algorithm which is related to the aforementioned union-find problem?</p>