title: Detect cycle in a graph using Kruskal's algorithm
body: <p>I'm implementing Kruskal's algorithm, which is a well-known approach to finding the minimum spanning tree of a weighted graph. However, I am adapting it to find cycles in a graph. This is the pseudocode for Kruskal's algorithm:</p>
  
  <pre><code>KRUSKAL(G):
  1 A = ∅
  2 foreach v ∈ G.V:
  3    MAKE-SET(v)
  4 foreach (u, v) ordered by weight(u, v), increasing:
  5    if FIND-SET(u) ≠ FIND-SET(v):
  6       A = A ∪ {(u, v)}
  7       UNION(u, v)
  8 return A
  </code></pre>
  
  <p>I'm having a hard time grasping the <code>FIND-SET()</code> and <code>MAKE-SET()</code> functions, or their implementation with the disjoint-set data structure.</p>
  
  <p>My current code looks like this:</p>
  
  <pre><code>class edge {
      public:      //for quick access (temp) 
        char leftV;
        char rightV;
        int weight;
  };
  
  std::vector&lt;edge&gt; kruskalMST(std::vector&lt;edge&gt; edgeList){
      std::vector&lt;char&gt; set;
      std::vector&lt;edge&gt; result;
      sortList(edgeList);    //sorts according to weight ( passed by reference)
      do{
          if(set.empty()){
              set.push_pack(edgeList[i].leftV);    //also only push them when
              set.push_pack(edgeList[i].rightV);    //they aren't there , will fix
              result.push_back(edgeList[i]);
              ++i;
          }
          else {
              if((setContains(set , edgeList[i].leftV)) &amp;&amp; (setContains(set , edgeList[i].rightV)))
                  ++i; //skip node 
              else {
                  set.push_pack(edgeList[i].leftV);    //also only push them when
                  set.push_pack(edgeList[i].rightV);    //they aren't there , will fix
                  result.push_back(edgeList[i]);
                  ++i;
              }
       } while(i&lt;edgeList.size());
      return result;
  }
  </code></pre>
  
  <p>My code detects a cycle in a graph when two vertices which are already present in <code>set vector</code> appear again. This seemed to work in most cases until I encountered a situation like this:</p>
  
  <pre><code>  [a]              [c]
     |                |
     |                |
     |                |
    [b]              [d]
  </code></pre>
  
  <p>When these edges appear in sorting order, this happens because <code>a</code>, <code>b</code>, <code>c</code>, <code>d</code> have already been pushed into <code>set vector</code>. Joining <code>[a]</code> to <code>[c]</code> doesn't produce a cycle inside the graph but is detected as a cycle due to current implementation.</p>
  
  <p>Is there any viable alternative to detect cycles in my case? Or if someone could explain how <code>MAKE-SET</code>, <code>FIND-SET</code>, and <code>UNION</code> work in Kruskal's algorithm, that would help a lot.</p>