Facebook
From Putrid Hornbill, 1 Week ago, written in Java.
Embed
Download Paste or View Raw
Hits: 66
  1. class Vertex
  2. {
  3.   // for all i in [0..next.length-1]
  4.   // there is an edge from `this` to `next[i]`  
  5.   Vertex[] next;
  6.   int mark;
  7.  
  8.   static bool HasCycle(Vertex[] vertices)
  9.   {
  10.     bool Inner(Vertex v)
  11.     {
  12.       if (v.mark == 1) return true;
  13.  
  14.       v.mark = 1;
  15.       foreach (var n in v.next)
  16.         if (Inner(n)) return true;
  17.  
  18.       v.mark = 0;
  19.       return false;
  20.     }
  21.     try
  22.     {
  23.       foreach (var v in vertices)
  24.         if (Inner(v)) return true;
  25.     }
  26.     finally
  27.     {
  28.       foreach (var v in vertices)
  29.         v.mark = 0; //clear marks for purity
  30.     }
  31.  
  32.     return false;
  33.   }
  34. }
  35.