{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "80140856",
   "metadata": {},
   "source": [
    "## See detailed notes in [vishnu.uk/blogs/algorithms](http://vishnu.uk/blogs/algorithms.html#cycles-in-undirected-graphs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "9e837c76",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>.container { width:100% !important; }</style>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from IPython.display import display, HTML\n",
    "display(HTML(\"<style>.container { width:100% !important; }</style>\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "cc73c891",
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "def draw_graph(graph):\n",
    "    G = nx.Graph(graph)\n",
    "    pos = nx.spring_layout(G)\n",
    "    plt.figure(figsize=(4,2))\n",
    "    nx.draw(G,pos, with_labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e0210c46",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAS4AAACeCAYAAACM/eeCAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjYuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8o6BhiAAAACXBIWXMAAAsTAAALEwEAmpwYAAAOS0lEQVR4nO3df2zU933H8df3fuAz2GfzwwaMyRAxcLANNqCtm2ZgqmqJrKxJVdOS4mhaljWryaRN2zQp7joN1VPZ1LGkwqVjiTYFbaOxqjRtvQ5SMGVKrBVITNbYOI6gsRMfnA32+YLvfL/2BzHYvjvbZ9/5/DHPh2TJuu/n+/l+7o976fP9vj/f79eKx+NxAYBBbLkeAACki+ACYByCC4BxCC4AxiG4ABiH4AJgHIILgHEILgDGceR6AMBC0BcIqelCjzq8fvmDEbldDnlWubV3R7mWF+TlengLjsXKeWDm2roHdKSlS2c7fZKkUCR2Z5vLYVNcUtWmEtXtrtC2tcW5GeQCRHABM3S89aoamjsUjEQ12a/IsiSXw676ao9qK9fN2fgWMq5xATNwO7TaNRxOHVp9Pz6smz9/SfG4NByOqqG5Xcdbr87pOBcqggtIU1v3gBqaOzQcjk3deIzhcEwNzR261DOQnYHdQ7g4D6TpSEuXgpHojPYNRqJqbOnS0dqdGR5V9s2nAgTBBaShLxDS2U5f0tPDEe976v+v5xW++aHy1++UrMQ28bh05rJP/YGQMdXGyQsQXh1+rXPOCxAEF5CGpgs9ST+PR8O6/oNvyr3zURXueES33m1V36v/IHdlTUJbS1LTxR49vev+tI8/17OeqQoQwY9D7OQ71/Tzzr45K0AQXEAaOrz+cTOOUaEPLkuxqAo/8agsy9ISz4Ma+sUrSfsIRmLq6B1K67i5mPXcLUBMfS1vbAFCUtbDi4vzQBr8wUjSz6OBftkLlsuy7p4f2t2lk/QTnvYxj7de1b5jrTrVfk2hSCwhOIMff3bynWvad6w1I5XL+V6AILiANLhdyU9S7AXLFA30a+yyyKjfl7Kf6PCQYrGpQ2E6yy5GZXLZRSYKENlEcAFp8KxyK8+R+LPJW+ORbHYNnX9V8WhEty6/rlBvZ9I+bPGIzv3ohEpLS1VTU6PGxka1t7dr4lrwXM16JitASFLE79P1HzSo+7mvqPufHteNk98dt31sASJbCC4gDTU7ypN+btmdKvnCswq8/TN1P/e4Pmo/p8UbH0ja1ulcpP898bza2tr02GOP6fz583r44YdVVlam/fv364UXXtCVK1dyNutJVYCQpHgsqusv/60c7lKt+dqLKn/m37R4866EdqMFiGzh4jyQhhUFedq9sUSn2q8lzEjyVm9Q2ZPPT7q/ZUl7NpXcrgAWrFFtba1qa2sVj8d15coVnT59WqdPn9bXv3lIeXv/XrI7E/oYfONlBdr+W9Fbg3IUrlDxrie0eNP4kJzpsouRkRG1/cqXtAAhSSO9nYoGbmjpZ5+UZbNLklxrfz2h3UwKEOkguIA0Haiq0Ll3+zQcTn825HLYVVdVkfC5ZVlav3691q9fr6eeekpHz3bpH091aiSaeL7mWLpaK/cfkr1gqW51/I/6fvxtla3xyFGwbFy7WDSqZ//lVW1b5JPf75ff79fg4OCd/yf+DQ4OKhqNauXev5Hj13476fgj/j45ikrvhNZk0ilApIvgAtK0bW2x6qs9014qMCrfaVN9tUdby4unbNvhHUoaWpK0xPPg3f8379LgGy9r5MNOOTZWjmsXjlu6+N412SK/VFFRkdxut8rKyuR2u+V2u+98NvbP5XLpz77/ll5568Okx3a4Vyji9ykei04ZXm5X4mwxUwguYAZG1yll6+kQqZZdSFLg7Z/J/4tXFBm8LkmKjwwrOuxP2nbrzk/pu7//zLSOOep2AcKb9HRx0eqNsi9ZqoGWf1XRg/tl2WwKebvkKt8yrp3LYZNndWFax00HwQXMUG3lOm0tL1ZjS5fOXPbJ0t2V5NLd53Ht2VSiuqqKac20RqVadhEZvK7+n35HK/c1KG+NR5bNrg9f/BNJyZNzJrOemh3lOvxa8oqoZbOrtOYbuvHaP+uDxj+QLEtLtuxOCK64pJrtyQsZmUBwAbOwtbxYR2t3qj8QUtPFHnX0DskfDMvtcsqzulA122d2K06qWU8sHJRkyb64SJIUuHRKYd+vkvYx01nPZAUISXIUlar0i19Puf+4AkSWEFxABiwvyJvRvYeppJr1LFpxn9yf/IK8L/2FZNm05Df2KG/CbGfUbGY92ShAZBJPQAXmqa++dD7lrGcqliU9tGXlrB6fk869iqNuFyA2c68icK86UFUhl2PqZQfJZGLWU1u5TvXVm5XvtMtK8oiesSxLynfa5yS0JGZcwLw2H2Y9l3oGslKAmA2CC5jn5stLOTJdgJgNggswwHyc9eQSwQUYZD7NenKJ4AJgHKqKAIxDcAEwDsEFwDgEFwDjEFwAjENwATAOwQXAOAQXAOMQXACMQ3ABMA7BBcA4BBcA4xBcAIxDcAEwDsEFwDgEFwDjEFwAjENwATAOwQXAOAQXAOMQXACMQ3ABMA7BBcA4BBcA4xBcAIxDcAEwDsEFwDgEFwDjEFwAjENwATAOwQXAOAQXAOMQXACMQ3ABMA7BBcA4BBcA4xBcAIxDcAEwDsEFwDgEFwDjEFwAjENwATAOwQXAOAQXAOMQXACMQ3ABMA7BBcA4BBcA4xBcAIxDcAEwDsEFwDgEFwDjEFwAjENwATAOwQXAOAQXAOMQXACMQ3ABMA7BBcA4jlwPIBv6AiE1XehRh9cvfzAit8shzyq39u4o1/KCvFwPD8AsWfF4PJ7rQWRKW/eAjrR06WynT5IUisTubHM5bIpLqtpUorrdFdq2tjg3gwQwawsmuI63XlVDc4eCkagm+0aWJbkcdtVXe1RbuW7OxgcgcxbENa7bodWu4fDt0OppfFLDV99K2jYel4bDUTU0t+t469U5HSeAzDA+uNq6B9TQ3KHhcGzqxmMMh2NqaO7QpZ6B7AwMQNYYH1xHWroUjERntG8wElVjS1eGRwQg23JSVcxU1a8vENLZTl/Sa1ojvZ26eep7igZuKH/jp7X8oTpZjkXj2sTj0pnLPvUHQlQbAYPMaXBNXvXz6vBrnWlV/Zou9KTc9tEvW1T65YOynC75mg5q4PUTWrrriYR2lqSmiz16etf9aX8fALkxZ6eKx1uvat+xVp1qv6ZQJDYutCQp+PFnJ9+5pn3HWqd14bzD60/oZ1ThjkfkcJfInl+ooge+pFvvnE3aLhiJqaN3KO3vAyB35mTGdbfqN/UF9LFVP0mTLlnwByMpt9kLS+7+7y5VNHBjkn7CU44LwPyR9RlXtqp+Xq9Xgz5vyv2jQ767//t9shcsS9nW7XKmNTYAuZX1GVeqql9kqF83T31Pwe7/k7UoX+5PPCr3zs+PazNa9Xtu72/qzTffVGtr650/v9+vit/7muxllYomyd+hiz9R/v2flOXM0+Ab39fizb+TdHwuh02e1YWZ+bIA5kRWgytV1S8ej8nXdFD5Gyq14tG/VGSoX9f/o17OZWuUv37HmHbSTy/1aPmfPqKN95WpsrJS1dXVOnjwoDZs2KD+j0b0mUOnFU1ynWvJlt26fuKvFQnc0OINn1LRA19OOsa4pJrt5Zn82gCyLKvBlarqN9L7rqLDfhU/+LgkyVm8SgW/9ZA+aj83Lrgkyel06lv/2aJnPudJ6GdFQZ52byzRqfZr48KxvO5FSVLRp7806fgsS9qzqYSlEIBhshpcqap+kcHrig716/3DY2ZB8ZjyyrcktA3HpPf6gymPcaCqQufe7dNwOP1FqC6HXXVVFWnvByC3shpcqap+DvcKOYpXas3Tx6bZT+qq37a1xaqv9ky7ajkq32lTfbVHW8uLp70PgPkhq1VFtyt5Li5avVG2RYs12NqkWDikeCyqEd9VhXo7U/QzedWvtnKd6qs3K99pl2VNPibLkvKddtVXb+bpEIChsjrj8qxyK8/hTThdtGx2ldR8QzdPv6APjv6hFAnLsbxcxUlWtk+36ldbuU5by4vV2NKlM5d9snR7cenYfuK6fU2rrqqCmRZgsKw+j6svENJnDp1Oubp9OvIcNr3+V59N6wJ6fyCkpos96ugdkj8YltvllGd1oWq28wRUYCHI6owrVdVvumZa9VtekMe9h8AClvWV8weqKuRy2Ge0L1U/AMlkPbhGq375zvQORdUPQCpzcpP1aPWOZ8IDyIQ5fVnGpZ4Bqn4AZi0nb/mh6gdgNhbM68kA3DuMf1kGgHsPwQXAOAQXAOMQXACMQ3ABMA7BBcA4BBcA4xBcAIxDcAEwDsEFwDgEFwDjEFwAjENwATAOwQXAOHPyBFRgIegLhNR0oUcdXr/8wYjcLoc8q9zau4PnyM01nscFTKGte0BHWrp0ttMnSeNetzf65N6qTSWq212hbWuLczPIewzBBUzieOtV3pUwD3GqCKRwO7TaNRxOfKFxuL9Hvh8eUmTAq+JdT8i98/MaDkfV0NwuSYRXljHjApJo6x7QvmOtGg5Hk27va35OtkWLtexzf5SwLd9p14mvVvLClyyiqggkcaSlS8FI8tCSpOjgdTlL7ku6LRiJqrGlK1tDgwguIEFfIKSznb6U17S8//6sgu+/rRsnj+r9b9cofOODcdvjcenMZZ/6A6E5GO29ieACJmi60DPp9lVf+TvllW/Rst/9Y933501yLluT0MaS1HRx8n4wcwQXMEGH1z9uycNMBCMxdfQOZWhEmIjgAibwByMZ6ieckX6QiOACJnC7MrNKyO1yZqQfJCK4gAk8q9zKc8zup+Fy2ORZXZihEWEigguYoGZH+az7iEuq2T77fpAcwQVMsKIgT7s3lsiyUrdZtf9bKtz2UNJtliXt2VTCjddZRHABSRyoqpDLYZ/Rvi6HXXVVFRkeEcYiuIAktq0tVn21R/nO9H4i+U6b6qs93O6TZdxkDaQweqM0T4eYf7jJGoBxOFUEYByCC4BxCC4AxiG4ABiH4AJgnP8HtcMHjYH/ZAYAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 288x144 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "non_cyclic_graph = {'a': {'c', 'd'}, 'b': {'e'}, 'c': {'a'}, 'd': {'a'}, 'e': {'b'}, 'f': {}}\n",
    "draw_graph(non_cyclic_graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "3a3da2f9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAS4AAACeCAYAAACM/eeCAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjYuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8o6BhiAAAACXBIWXMAAAsTAAALEwEAmpwYAAAQNUlEQVR4nO3de1BUV54H8O/tvg3dvGwREEcYHQVERyUVzIyjrkIqqynL1TKiUceUUdi4g0ltWWY3WTEmTC2TTLlblElpxRUTa8kyeZCprFll1scG1ynDbIK7mlVQSJaXEeUhjxa66b7d+wcBQbqbftJ97O/nL4p77rmnqOJb955z7+9INpvNBiIigagCPQAiIncxuIhIOAwuIhIOg4uIhMPgIiLhMLiISDhyoAdAJLJ2gwnl1S2obe1Bj9GCGK2M9MQYbMxMwpSo8EAP75El8T0uIvddae7C4cp6XLjZBgAwWazDx7SyCjYAWXPikb8iBRnJ+sAM8hHG4CJy0wdVDSg6XQujRYGz/x5JArSyGgWr07Ft8cwJG18o4KMikRsGQ6sG/WbruG1tNqDfrKDodA0AMLx8iJPzRC660tyFotO1LoXWSP1mK4pO1+JqS5d/BhaCeMdF5KLDlfUwWhS7xyw9beg8908wNV8DbDZEzluO2JW/Gj5utCg4UlmPd7ctmqjhPtIYXEQuaDeYcOFmm905LZtVwd1PCqGdkYG4X+2FpFLBdLtudBsb8MWNNnQYTFxt9AE+KhK5oLy6xeGxgds3oRg6MfnJnVCFaSHJYdAm/3RMOwlA+WXH/ZDrGFxELqht7Rn1ysNIlp52yJMSIKnUTvswWqyovd3rj+GFHAYXkQt6jBaHx+SYOFh62mCz2p//Gt2P2ZfDClkMLiIXxGgdTweHTUuDOnIyuipPwDpghM0yAGPLdQf9aPw1xJDC4CJyQXpiDMJl+/8ukkqNhJwDMN+7jVtHdqDl8PPoq7k4pp1WViF9WrS/hxoS+OY8kQvaDSYs/e1/OJznckW4rMKlV57kqqIP8I6LyAVxUeFYkRYPSfLsfEkCsufEM7R8hMFF5KLdWSnQys5XDh0Jl1XIz0rx8YhCF4OLyEUZyXoUrE6HTuPev43KasHk//sCc+J1fhpZ6GFwEblh2+KZKFg9FzqNetzHRkkCdBo1Xl87Hz/q+xabNm3CwMDAxAz0EcfJeSIPXG3pwpHKenxxow0SBl8uHTJUjyt7Tjzys1KwMEmPgYEBbNy4EbIs48MPP4RGw9civMHgIvJCh8GE8sstqL3dix6jGTFaDdKnRSPn8bEVUE0mEzZs2ICIiAiUlZVBlvmpsKcYXEQTyGg0Yv369dDr9SgtLX2kwmsiy1gzuIgmWH9/P9auXYvExEScOHECarVnK5XBIhBlrBlcRAHQ19eHNWvWYMaMGTh+/DhUKjHXyQJVxlrMvxaR4CIiIvD555/ju+++w65du2C1ev5GfqA8KGP9ILRajuxEf8P/jGk7soz1B1UNXl+bwUUUIJGRkTh16hRqamqQn58PkR5+Al3GmsFFFEBRUVGoqKjA1atX8dJLLwkTXs7KWI9nqIy1Nx6dJQ0iQUVHR6OiogIrV67Enj17UFxcDGnE263BtumsszLWwGBF2Htnj0IxdEKX9gtMWZUPSQ4bPu6LMtacnCcKEl1dXXjqqaeQlZWFgwcP4mpLd1BuOvvuhW9RfO6m3UoZLUcGy1cnbCqEpNGirfzXCJ+xEJOXPzeqnVZWYc+fp2HX8tkejYGPikRBQq/X48yZMzh//jxy/u4Qnj32Jc7W3IHJYh0TEsYffnfm+h1sPlblkwlvVzkrYw0A0ZlrIMfEQ62LxqQlm9B3/cKYNt6WsWZwEQWR2NhY7PqHf0G1MgNGs9XpKwaA71frxmOxWNDa0e20jTo6/sHPMQlQDJ1223lTxppzXERB5EpzFw5daAJGzAm5Ymi1bmGSHguT9F6NwWKxoKmpCXV1dairq0N9ff3wz42NjUhc/wqkn/zc4flKb9uDn3vaoI6KtdvOmzLWDC6iIOKL1TpXNp1VFAWNjY2jQmno58bGRkydOhUpKSlITU1FamoqsrOzkZqailmzZuHEn245nOMCgN7Lp6Cb/TNImnB0f/kxIub+2Zg23paxZnARBQlnq3XdX34Cw5V/h9LXDTk6DvrlzyFizpJRbR5erVMUZfjO6eGAamhoQEJCAlJTU4cDKjs7GykpKZg1axZ0Ose1w3Iyk1B87qbD45HzVuDuR6/BYuhEROrPMWnJs2Pa2ADkPJ7k8t/mYVxVJAoSzlbr7tf+EeHT50IdNRl9tX9Ex+lD+NGuY5AfegxT2RQktP4XuqrK0dDQgPj4+OG7ppF3UOOF03heKP0aZ2vujDsHZ48kAavmTXXpztAR3nERBQlnq3WR6cse/Dx3Obq//AQD39+EnLZ4VDurpEbS/J+h5OXNmD17tlfh5MzurBRcrGtHv9n9x1qtrPa6jDWDiyhIONt01vDNefR89Rks3XcBALaBfij9PXbbToqfhvnz5/tljEOGylgPfqvo+mc/Oo0KBavTvV5AYHARBQlHm85auu+i4w/vYOrmIoRPT4ekUuP7917C4EyRvX4mprrqUJWHQFSHYHARBYnBTWdbxzwuWs1GABLUEZMAAIarZ2Fua7Tbh0YFzEmcuE1nty2eiYVJehyprMf5mjswm82A+kFw2itj7QucnCcKEnd7+rHkrfOw2MbuwnHvwj/D8N+nAUmFyPnZGGj9FpHzsxGdsWp0Q8WMsIpfI3fbs9i+fTsSExMnaPTA6785iK87ZaQ9kT1uGWtvMbiIAsxms6GiogIFBQW4//gvYU6Y6+Ah0DlJAlbOm4odKRaUlJTg008/RVZWFnJzc/H000/7vUz0mjVrsGPHDmzYsMGv1wEYXEQBdfHiRezbtw+dnZ0oKirCzMwV2HLsTx6t1uk0anz0wuLhx7He3l58/PHHKCkpQVNTE55//nns3LkTs2d79mGzM1arFXFxcbh+/fqE3OUxuIgCoLq6Gvv378eNGzdQWFiIrVu3Dteef1BZ1N3VurkOJ76vXbuG48ePo7S0FAsWLEBeXh6eeeYZaLVaj8b/cKkdq/E+/vNkGb766J0JKbXD4CKaQDU1NThw4AAuXbqE/fv3Izc3F2FhY79L9Fctd5PJhJMnT6KkpATV1dXYsmUL8vLykJGR4dL4nW2MobJaoAkLm5BSOwwuognQ0NCAwsJCnDp1Ci+//DJefPFFREREOD3H3U1n3dXY2Ij3338f7733HhISEpCXl4ctW7Zg0qRJdtsHamMMu9dgcBH5T2trK4qKilBWVobdu3dj7969DoPBEXc2nfWEoig4d+4cSkpKcPbsWaxbtw55eXlYtmzZcCVWfzy+eoPBRWSHt+WS7927h4MHD+Lo0aPYvn07Xn31VSQkJEzAyL3T1taG0tJSlJSUQFEU5ObmYtHKDdj9+zqfLBj4CoOLaARvNzc1GAx4++23UVxcjPXr1+O1115DcnLyBI3ed2w2G6qqqlBSUoIKQzLCfpIJSKPrjlp6O3Dv7FEYm/8XUpgOMU+sQ8yitaPa+OKDansYXEQ/8GYOx2Qy4ejRo3jzzTeRlZWFwsJCpKWlTczA/ajdYMKSt85jQBn9B7HZrGg9sQe61MWY9IscWHo7cPd3BYhdlQ/drMxRbcNlFS698qRPVxv5yQ8RXJvDaf+3Yqhj4jB5+XPD5ZIVxQrrzQt44403sGDBAlRUVOCxxx6buIH7WXl1yw/zXKODa+B2HZT+HuiXbQEAaPSJiHpsFe7XXBwTXBKA8sstHm+MYQ+Di0KeN5ubvv7ZFSRe+wPKysqwdOlSP40wcByV2rF034XS24Gm4hFFAm1WhCfNG9PW240x7GFwUcjzplyyJIchY+vfYOlS387hBAtHpXbkmDjI+qmYvuuYi/14vjGG3ev7tDciwTgrlzzQ+i06Kt6G+d730M1aNPjM8xAbgEovNzcNZo5K7YRNS4MqLALdVeWIzvwLSGoZ5o5m2CwDCJ82dm7P16V2uD0ZhbTy6ha7v7cpZtz9/d8j8qfZSP7r3yEifSn6blyy23ZoDudRNFhqZ2xMSCo14nMOYODOd7j1bi5aDm1FR8U7sJr6xrT1dmMMe3jHRSHN0RyO6dYNwKog+ol1kCQJkenL0PvVZ3b78MccTrBwtjGGHD0F8ev+dtw+vN0Ywx7ecVFIczSHoxg6oI6aMvzmODC4uanjfnw7hxMs4qLCsSItHpKdx2RXSNLgZ0m+foxmcFFIczSHo46KhWLowMjXHJWeNrttB/uZmHLJgbA7KwVaWe3Rub7YGMMeBheFNEdzOOHT0wGVGr1fn4RNsaDvxiWYbtt/ZPLHHE4wGdoYQ6dxLy58tTGGPQwuCmk5mfbnXiS1BvHr98HwzXk0H9qC+zUXEZG2xG5bf8zhBJtti2eiYPVc6DTqcR8bJWnwG0V/fWAN8JMfooBvbioSf5facRWDi0LeleYubD5WFVTVD4Kdv0vtjIfBRYTgqzdFzvE9LiIEdnNTch/vuIhGCJY5HHKOwUVkR6DncMg5BhcRCYfvcRGRcBhcRCQcBhcRCYfBRUTCYXARkXAYXEQkHAYXEQmHwUVEwmFwEZFwGFxEJBwGFxEJh8FFRMJhcBGRcBhcRCQcBhcRCYfBRUTCYXARkXAYXEQkHAYXEQmHwUVEwmFwEZFwGFxEJBwGFxEJh8FFRMJhcBGRcBhcRCQcBhcRCYfBRUTCYXARkXAYXEQkHAYXEQmHwUVEwmFwEZFwGFxEJBwGFxEJh8FFRMJhcBGRcBhcRCQcBhcRCYfBRUTCYXARkXAYXEQkHAYXEQmHwUVEwmFwEZFwGFxEJBwGFxEJh8FFRMJhcBGRcBhcRCQcBhcRCYfBRUTCYXARkXAYXEQkHAYXEQmHwUVEwmFwEZFwGFxEJBwGFxEJh8FFRMJhcBGRcBhcRCQcBhcRCYfBRUTCkX3RSbvBhPLqFtS29qDHaEGMVkZ6Ygw2ZiZhSlS4Ly5BRDRMstlsNk9PvtLchcOV9bhwsw0AYLJYh49pZRVsALLmxCN/RQoykvXejpWICIAXwfVBVQOKTtfCaFHgrAdJArSyGgWr07Ft8UwPh0lE9IBHj4qDoVWDfrN11O/NHS1o+9ffwtLVCv3y5xCzaC1sNqDfrKDodA0AMLyIyGtu33Fdae7C5mNV6DcrY461nz4EVVgEYp/6S7vn6jRqfPTCYixM0ns0WCIiwINVxcOV9TBaxoYWACjdd6GJ/7HDc40WBUcq6929JBHRKG4FV7vBhAs32+zOabWW7YOx6Rt0nnkXTf+YA3PnrTFtbDbgixtt6DCYPB4wEZFbwVVe3eLwWOLW3yA8aR5iV/4Vfry3HJrY6XbbSQDKLzvuh4hoPG4FV21rz6hXHjxhtFhRe7vXqz6IKLS5FVw9RotPLtpjNPukHyIKTW4FV4zWJy/aI0ar8Uk/RBSa3Aqu9MQYhMvefd6olVVInxbtVR9EFNrcSqGczCSvL2gDkPO49/0QUehyK7jiosKxIi0ekmT/eOIv30J0xiqH50sSkD0nnh9eE5FX3H7u252VAq2s9uhiWlmN/KwUj84lIhridnBlJOtRsDodOo17p+o0KhSsTufnPkTkNY+WCYc+lGZ1CCIKBK/qcRERBQJLNxORcBhcRCQcBhcRCYfBRUTCYXARkXD+H+EU48+crwL9AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 288x144 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cyclic_graph = {'a': {'c', 'd', 'e', 'b'}, 'b': {'e', 'a'}, 'c': {'a'}, 'd': {'a'}, 'e': {'b', 'a'}, 'f': {}}\n",
    "draw_graph(cyclic_graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b96c54c",
   "metadata": {},
   "source": [
    "### Check if cycles exist in an undirected graph using `Disjoint Union Sets`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "3be4f2b1",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections.abc import Iterable\n",
    "from dataclasses import dataclass\n",
    "from dataclasses import field\n",
    "from typing import Generator\n",
    "from typing import Hashable\n",
    "\n",
    "@dataclass\n",
    "class DSU:\n",
    "    \"\"\"Disjoint union set implementation.\"\"\"\n",
    "\n",
    "    parent: dict[Hashable, Hashable] = field(default_factory=dict)\n",
    "    rank: dict[Hashable, int] = field(default_factory=dict)\n",
    "\n",
    "    def add_nodes(self, ns: Iterable[Hashable]) -> 'DSU':\n",
    "        for n in ns:\n",
    "            self.add_node(n=n)\n",
    "        return self\n",
    "\n",
    "    def add_node(self, n: Hashable) -> 'DSU':\n",
    "        self.parent[n] = n\n",
    "        self.rank[n] = 1\n",
    "        return self\n",
    "\n",
    "    def find_leader(self, n: Hashable) -> Hashable:\n",
    "        if self.parent[n] == n:\n",
    "            return n\n",
    "        self.parent[n] = self.find_leader(n=self.parent[n])\n",
    "        return self.parent[n]\n",
    "\n",
    "    def union(self, n1: Hashable, n2: Hashable) -> 'DSU':\n",
    "        n1_leader = self.find_leader(n=n1)\n",
    "        n2_leader = self.find_leader(n=n2)\n",
    "        if n1_leader == n2_leader:\n",
    "            return\n",
    "        if self.rank[n1_leader] > self.rank[n2_leader]:\n",
    "            self.parent[n2_leader] = n1_leader\n",
    "        elif self.rank[n1_leader] < self.rank[n2_leader]:\n",
    "            self.parent[n1_leader] = n2_leader\n",
    "        else:\n",
    "            # equal ht trees\n",
    "            self.parent[n2_leader] = n1_leader\n",
    "            self.rank[n1_leader] += 1\n",
    "        return self\n",
    "\n",
    "    def is_connected(self, n1: Hashable, n2: Hashable) -> bool:\n",
    "        return self.find_leader(n=n1) == self.find_leader(n=n2)\n",
    "\n",
    "def has_undirected_cycle_dsu(graph: dict[str, set[str]]) -> bool:\n",
    "    \"\"\"Finds cycles in an undirected graph.\n",
    "\n",
    "    :param graph: The keys of the dict are the graph nodes which are strings. The set\n",
    "        of strings they hold are the set of nodes connected to them.\n",
    "    \"\"\"\n",
    "    dsu = DSU()\n",
    "    dsu.add_nodes(ns=graph.keys())\n",
    "    for n1, n2 in _iter_edges(graph):\n",
    "        if dsu.is_connected(n1, n2):\n",
    "            return True\n",
    "        dsu.union(n1, n2)\n",
    "    else:\n",
    "        return False\n",
    "    \n",
    "def _iter_edges(graph: dict[str, set[str]]) -> Generator[tuple, None, None]:\n",
    "    \"\"\"Iterate through edges in a undirected graph. In an undirected graph, two\n",
    "    connected nodes A and B will have each other in their edge set and hence the edge\n",
    "    appears twice, we have to ensure we only yield an edge once.\n",
    "    \"\"\"\n",
    "    seen = set()\n",
    "    for n, adjs in graph.items():\n",
    "        for adj in adjs:\n",
    "            edge = tuple(sorted([n, adj]))\n",
    "            if edge in seen:\n",
    "                continue\n",
    "            seen.add(edge)\n",
    "            yield edge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d178eb0d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dsu.is_connected('a', 'c')=True, dsu.is_connected('b', 'e')=True, dsu.is_connected('b', 'a')=False\n"
     ]
    }
   ],
   "source": [
    "dsu = DSU()\n",
    "dsu.add_nodes(['a', 'b', 'c', 'd', 'e'])\n",
    "dsu.union('a', 'd').union('b', 'e').union('c', 'd')\n",
    "print(f\"{dsu.is_connected('a', 'c')=}, {dsu.is_connected('b', 'e')=}, {dsu.is_connected('b', 'a')=}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "0c6f0d1b",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "has_undirected_cycle_dsu(non_cyclic_graph)=False\n",
      "has_undirected_cycle_dsu(cyclic_graph)=True\n"
     ]
    }
   ],
   "source": [
    "print(f\"{has_undirected_cycle_dsu(non_cyclic_graph)=}\")\n",
    "print(f\"{has_undirected_cycle_dsu(cyclic_graph)=}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "513e38ff",
   "metadata": {},
   "source": [
    "### Check if cycles exist in an undirected graph using `DFS`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "3e6578b9",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Optional\n",
    "\n",
    "def has_undirected_cycle_dfs(graph: dict[str, set[str]]) -> bool:\n",
    "    seen = set()\n",
    "    # The graph may not be fully connected, we need to DFS through each connected set.\n",
    "    for n in graph:\n",
    "        if n in seen:\n",
    "            continue\n",
    "        if _ucycle_dfs(graph=graph, node=n, parent=None, seen=seen):\n",
    "            return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def _ucycle_dfs(\n",
    "        graph: dict[str, set[str]], node: str, parent: Optional[str], seen: set) -> bool:\n",
    "    seen.add(node)\n",
    "    for adj in graph[node]:\n",
    "        if adj == parent:\n",
    "            continue\n",
    "        elif adj in seen:\n",
    "            # We have reached neighbour before through different path, this is a cycle.\n",
    "            return True\n",
    "        elif _ucycle_dfs(graph=graph, node=adj, parent=node, seen=seen):\n",
    "            return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "e5a223da",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "has_undirected_cycle_dfs(non_cyclic_graph)=False\n",
      "has_undirected_cycle_dfs(cyclic_graph)=True\n"
     ]
    }
   ],
   "source": [
    "print(f\"{has_undirected_cycle_dfs(non_cyclic_graph)=}\")\n",
    "print(f\"{has_undirected_cycle_dfs(cyclic_graph)=}\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}