title: Most efficient way of finding circular references in list
body: <p>Given the following list of redirects</p>
  
  <pre><code>[
      {
          "old": "a",
          "target": "b"
      },
      {
          "old": "b",
          "target": "c"
      },
      {
          "old": "c",
          "target": "d"
      },
      {
          "old": "d",
          "target": "a"
      },
      {
          "old": "o",
          "target": "n"
      },
      {
          "old": "n",
          "target": "b"
      },
      {
          "old": "j",
          "target": "x"
      },
      {
          "old": "whatever",
          "target": "something"
      }
  ]
  </code></pre>
  
  <p>Here we can see that the first item "a" should redirect to "b".
  If we follow the list we can see the following pattern:</p>
  
  <pre><code>a -&gt; b
  b -&gt; c
  c -&gt; d
  d -&gt; a
  </code></pre>
  
  <p>So we would end up with a circular reference since "a" would end up pointing to "d" and "d" points to "a".</p>
  
  <p>What would be the most efficient way of finding the circular references?</p>
  
  <p>I've come up with the following algorithm in C#</p>
  
  <pre><code>var items = JsonConvert.DeserializeObject&lt;IEnumerable&lt;Item&gt;&gt;(json)
      .GroupBy(x =&gt; x.Old)
      .Select(x =&gt; x.First())
      .ToDictionary(x =&gt; x.Old, x =&gt; x.Target);
  var circulars = new Dictionary&lt;string, string&gt;();
  foreach (var item in items)
  {
      var target = item.Value;
      while (items.ContainsKey(target))
      {
          target = items[target];
  
          if (target.Equals(item.Key))
          {
              circulars.Add(target, item.Value);
              break;
          }
      }
  }
  </code></pre>
  
  <p>This will give me a list containing 4 items looking like this:</p>
  
  <pre><code>[
      {
          "old": "a",
          "target": "b"
      },
      {
          "old": "b",
          "target": "c"
      },
      {
          "old": "c",
          "target": "d"
      },
      {
          "old": "d",
          "target": "a"
      }
  ]
  </code></pre>
  
  <p>But im only interested in telling the user something like </p>
  
  <p><strong>"Hey you can't do that, It will be a circular reference because of "a" points to "b" which points to "c" which points to "d" which points to "a"</strong></p>
  
  <p>So, do you guys have any suggestions?
  Im sure that some other(better) algorithms exists for doing this... :)</p>