0904_ds_pathcompressionfind.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "0904-ds-pathcompressionfind.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyNDJ0W/pOl4VtGWSLPO1qou",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/lmcanavals/acomplex/blob/main/0904_ds_pathcompressionfind.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "import graphviz as gv"
      ],
      "metadata": {
        "id": "3Ji-nJEUEL9k"
      },
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def drawDS(ds):\n",
        "  graph = gv.Digraph(\"DisjointSet\")\n",
        "  graph.graph_attr['rankdir'] = \"BT\"\n",
        "  for e, p in enumerate(ds):\n",
        "    graph.node(str(e))\n",
        "    if p >= 0:\n",
        "      graph.edge(str(e), str(p))\n",
        "  return graph"
      ],
      "metadata": {
        "id": "DTDS5teOEOMb"
      },
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "ds = [-1, -1, -3, 2, 8, -2, 5, -1, -2, 2]\n",
        "drawDS(ds)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 175
        },
        "id": "2OYwdaktEr8A",
        "outputId": "925aae83-7c85-4176-e78f-aa78489fecbd"
      },
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7f207c96d150>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: DisjointSet Pages: 1 -->\n<svg width=\"494pt\" height=\"116pt\"\n viewBox=\"0.00 0.00 494.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\n<title>DisjointSet</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-112 490,-112 490,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"207\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"207\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 3&#45;&gt;2 -->\n<g id=\"edge1\" class=\"edge\">\n<title>3&#45;&gt;2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M179.7146,-35.4292C183.9597,-43.9193 189.1536,-54.3071 193.8663,-63.7326\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"190.763,-65.3523 198.3657,-72.7313 197.024,-62.2218 190.763,-65.3523\"/>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 8 -->\n<g id=\"node6\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 4&#45;&gt;8 -->\n<g id=\"edge2\" class=\"edge\">\n<title>4&#45;&gt;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M315,-36.1686C315,-43.869 315,-53.0257 315,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"311.5001,-61.5867 315,-71.5867 318.5001,-61.5868 311.5001,-61.5867\"/>\n</g>\n<!-- 5 -->\n<g id=\"node7\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 6 -->\n<g id=\"node8\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 6&#45;&gt;5 -->\n<g id=\"edge3\" class=\"edge\">\n<title>6&#45;&gt;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M387,-36.1686C387,-43.869 387,-53.0257 387,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"383.5001,-61.5867 387,-71.5867 390.5001,-61.5868 383.5001,-61.5867\"/>\n</g>\n<!-- 7 -->\n<g id=\"node9\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"459\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"459\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 9&#45;&gt;2 -->\n<g id=\"edge4\" class=\"edge\">\n<title>9&#45;&gt;2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M234.2854,-35.4292C230.0403,-43.9193 224.8464,-54.3071 220.1337,-63.7326\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"216.976,-62.2218 215.6343,-72.7313 223.237,-65.3523 216.976,-62.2218\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Quick Union"
      ],
      "metadata": {
        "id": "w5ExqVHRFDub"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def find(ds, e):\n",
        "  if ds[e] < 0:\n",
        "    return e\n",
        "  else:\n",
        "    ancestor = find(ds, ds[e])\n",
        "    ds[e] = ancestor\n",
        "    return ancestor"
      ],
      "metadata": {
        "id": "ddDGtDDPE0Lz"
      },
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "find(ds, 0), find(ds, 7), find(ds, 3), find(ds, 9), find(ds, 2)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "sKGDs9B_FMri",
        "outputId": "569556f4-849f-40f8-e3db-b53f884bd64b"
      },
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(0, 7, 2, 2, 2)"
            ]
          },
          "metadata": {},
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def union(ds, a, b):\n",
        "  a = find(ds,  a)\n",
        "  b = find(ds, b)\n",
        "\n",
        "  if a == b: return\n",
        "\n",
        "  if ds[a] <= ds[b]:\n",
        "    ds[a] += ds[b]\n",
        "    ds[b] = a\n",
        "  else:\n",
        "    ds[b] += ds[a]\n",
        "    ds[a] = b\n"
      ],
      "metadata": {
        "id": "55GySBVAFV-9"
      },
      "execution_count": 17,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "ds = [-1]*10\n",
        "drawDS(ds)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 79
        },
        "id": "1x3ns9AsFr3Q",
        "outputId": "2baacc5a-2b25-4447-979d-0e38c426c212"
      },
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7f206e5ada10>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: DisjointSet Pages: 1 -->\n<svg width=\"710pt\" height=\"44pt\"\n viewBox=\"0.00 0.00 710.00 44.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 40)\">\n<title>DisjointSet</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-40 706,-40 706,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 6 -->\n<g id=\"node7\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"459\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"459\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 7 -->\n<g id=\"node8\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"531\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"531\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 8 -->\n<g id=\"node9\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"603\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"603\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"675\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"675\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 18
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "union(ds, 3, 4)\n",
        "drawDS(ds)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 175
        },
        "id": "5-i3nCgOFvvn",
        "outputId": "e2039988-db0d-46b2-d14a-6ec06e517851"
      },
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7f206e5d5150>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: DisjointSet Pages: 1 -->\n<svg width=\"638pt\" height=\"116pt\"\n viewBox=\"0.00 0.00 638.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\n<title>DisjointSet</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-112 634,-112 634,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 4&#45;&gt;3 -->\n<g id=\"edge1\" class=\"edge\">\n<title>4&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M243,-36.1686C243,-43.869 243,-53.0257 243,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"239.5001,-61.5867 243,-71.5867 246.5001,-61.5868 239.5001,-61.5867\"/>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 6 -->\n<g id=\"node7\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 7 -->\n<g id=\"node8\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"459\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"459\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 8 -->\n<g id=\"node9\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"531\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"531\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"603\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"603\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 19
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "union(ds, 4, 9)\n",
        "drawDS(ds)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 175
        },
        "id": "TW_55AswF5iZ",
        "outputId": "91f0ad6b-7b15-43e6-f525-3ceaf329c8b0"
      },
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7f206e5a3e90>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: DisjointSet Pages: 1 -->\n<svg width=\"638pt\" height=\"116pt\"\n viewBox=\"0.00 0.00 638.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\n<title>DisjointSet</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-112 634,-112 634,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"279\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"279\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 4&#45;&gt;3 -->\n<g id=\"edge1\" class=\"edge\">\n<title>4&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M251.7146,-35.4292C255.9597,-43.9193 261.1536,-54.3071 265.8663,-63.7326\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"262.763,-65.3523 270.3657,-72.7313 269.024,-62.2218 262.763,-65.3523\"/>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 6 -->\n<g id=\"node7\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"459\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"459\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 7 -->\n<g id=\"node8\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"531\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"531\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 8 -->\n<g id=\"node9\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"603\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"603\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 9&#45;&gt;3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>9&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M306.2854,-35.4292C302.0403,-43.9193 296.8464,-54.3071 292.1337,-63.7326\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"288.976,-62.2218 287.6343,-72.7313 295.237,-65.3523 288.976,-62.2218\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 20
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "union(ds, 8, 0)\n",
        "drawDS(ds)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 175
        },
        "id": "MWl5Q_5UF9ga",
        "outputId": "c3a6bf79-1d90-44b5-a8a7-2b77c884e175"
      },
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7f206e56cb10>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: DisjointSet Pages: 1 -->\n<svg width=\"566pt\" height=\"116pt\"\n viewBox=\"0.00 0.00 566.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\n<title>DisjointSet</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-112 562,-112 562,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 8 -->\n<g id=\"node2\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 0&#45;&gt;8 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M27,-36.1686C27,-43.869 27,-53.0257 27,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"23.5001,-61.5867 27,-71.5867 30.5001,-61.5868 23.5001,-61.5867\"/>\n</g>\n<!-- 1 -->\n<g id=\"node3\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 2 -->\n<g id=\"node4\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 3 -->\n<g id=\"node5\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"279\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"279\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 4 -->\n<g id=\"node6\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 4&#45;&gt;3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>4&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M251.7146,-35.4292C255.9597,-43.9193 261.1536,-54.3071 265.8663,-63.7326\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"262.763,-65.3523 270.3657,-72.7313 269.024,-62.2218 262.763,-65.3523\"/>\n</g>\n<!-- 5 -->\n<g id=\"node7\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 6 -->\n<g id=\"node8\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"459\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"459\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 7 -->\n<g id=\"node9\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"531\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"531\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 9&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>9&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M306.2854,-35.4292C302.0403,-43.9193 296.8464,-54.3071 292.1337,-63.7326\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"288.976,-62.2218 287.6343,-72.7313 295.237,-65.3523 288.976,-62.2218\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 21
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "union(ds, 2, 3)\n",
        "drawDS(ds)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 175
        },
        "id": "GpI_taPkGDCE",
        "outputId": "ed286402-e43d-4702-b383-c58463bd027c"
      },
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7f206e5706d0>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: DisjointSet Pages: 1 -->\n<svg width=\"566pt\" height=\"116pt\"\n viewBox=\"0.00 0.00 566.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\n<title>DisjointSet</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-112 562,-112 562,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 8 -->\n<g id=\"node2\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 0&#45;&gt;8 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M27,-36.1686C27,-43.869 27,-53.0257 27,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"23.5001,-61.5867 27,-71.5867 30.5001,-61.5868 23.5001,-61.5867\"/>\n</g>\n<!-- 1 -->\n<g id=\"node3\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 2 -->\n<g id=\"node4\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 3 -->\n<g id=\"node5\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 2&#45;&gt;3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>2&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M186.2693,-33.2693C196.197,-43.197 209.3153,-56.3153 220.4363,-67.4363\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"218.2067,-70.1564 227.7527,-74.7527 223.1564,-65.2067 218.2067,-70.1564\"/>\n</g>\n<!-- 4 -->\n<g id=\"node6\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 4&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>4&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M243,-36.1686C243,-43.869 243,-53.0257 243,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"239.5001,-61.5867 243,-71.5867 246.5001,-61.5868 239.5001,-61.5867\"/>\n</g>\n<!-- 5 -->\n<g id=\"node7\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 6 -->\n<g id=\"node8\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"459\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"459\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 7 -->\n<g id=\"node9\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"531\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"531\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 9&#45;&gt;3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>9&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M299.7307,-33.2693C289.803,-43.197 276.6847,-56.3153 265.5637,-67.4363\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"262.8436,-65.2067 258.2473,-74.7527 267.7933,-70.1564 262.8436,-65.2067\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 22
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "union(ds, 5, 6)\n",
        "drawDS(ds)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 175
        },
        "id": "OrPr8s7KGFAP",
        "outputId": "0b4de0cb-6bd5-4716-f338-bb020de2d0a9"
      },
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7f206e5a3450>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: DisjointSet Pages: 1 -->\n<svg width=\"494pt\" height=\"116pt\"\n viewBox=\"0.00 0.00 494.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\n<title>DisjointSet</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-112 490,-112 490,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 8 -->\n<g id=\"node2\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 0&#45;&gt;8 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M27,-36.1686C27,-43.869 27,-53.0257 27,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"23.5001,-61.5867 27,-71.5867 30.5001,-61.5868 23.5001,-61.5867\"/>\n</g>\n<!-- 1 -->\n<g id=\"node3\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 2 -->\n<g id=\"node4\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 3 -->\n<g id=\"node5\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 2&#45;&gt;3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>2&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M186.2693,-33.2693C196.197,-43.197 209.3153,-56.3153 220.4363,-67.4363\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"218.2067,-70.1564 227.7527,-74.7527 223.1564,-65.2067 218.2067,-70.1564\"/>\n</g>\n<!-- 4 -->\n<g id=\"node6\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 4&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>4&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M243,-36.1686C243,-43.869 243,-53.0257 243,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"239.5001,-61.5867 243,-71.5867 246.5001,-61.5868 239.5001,-61.5867\"/>\n</g>\n<!-- 5 -->\n<g id=\"node7\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 6 -->\n<g id=\"node8\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 6&#45;&gt;5 -->\n<g id=\"edge4\" class=\"edge\">\n<title>6&#45;&gt;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M387,-36.1686C387,-43.869 387,-53.0257 387,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"383.5001,-61.5867 387,-71.5867 390.5001,-61.5868 383.5001,-61.5867\"/>\n</g>\n<!-- 7 -->\n<g id=\"node9\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"459\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"459\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 9&#45;&gt;3 -->\n<g id=\"edge5\" class=\"edge\">\n<title>9&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M299.7307,-33.2693C289.803,-43.197 276.6847,-56.3153 265.5637,-67.4363\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"262.8436,-65.2067 258.2473,-74.7527 267.7933,-70.1564 262.8436,-65.2067\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 23
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "union(ds, 5, 9)\n",
        "drawDS(ds)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 271
        },
        "id": "EAdUqSCbGJwM",
        "outputId": "86f9f429-6c3c-4ff2-c9a9-7a94027d8058"
      },
      "execution_count": 24,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7f206e5b5ad0>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: DisjointSet Pages: 1 -->\n<svg width=\"350pt\" height=\"188pt\"\n viewBox=\"0.00 0.00 350.00 188.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 184)\">\n<title>DisjointSet</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-184 346,-184 346,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 8 -->\n<g id=\"node2\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 0&#45;&gt;8 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M27,-36.1686C27,-43.869 27,-53.0257 27,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"23.5001,-61.5867 27,-71.5867 30.5001,-61.5868 23.5001,-61.5867\"/>\n</g>\n<!-- 1 -->\n<g id=\"node3\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"135\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"135\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 2 -->\n<g id=\"node4\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 3 -->\n<g id=\"node5\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"207\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"207\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 2&#45;&gt;3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>2&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M118.3082,-102.8722C135.3555,-114.237 160.4019,-130.9346 179.5344,-143.6896\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"177.5969,-146.6044 187.8589,-149.2393 181.4799,-140.7801 177.5969,-146.6044\"/>\n</g>\n<!-- 4 -->\n<g id=\"node6\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 4&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>4&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M179.7146,-107.4292C183.9597,-115.9193 189.1536,-126.3071 193.8663,-135.7326\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"190.763,-137.3523 198.3657,-144.7313 197.024,-134.2218 190.763,-137.3523\"/>\n</g>\n<!-- 5 -->\n<g id=\"node7\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 5&#45;&gt;3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>5&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M234.2854,-107.4292C230.0403,-115.9193 224.8464,-126.3071 220.1337,-135.7326\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"216.976,-134.2218 215.6343,-144.7313 223.237,-137.3523 216.976,-134.2218\"/>\n</g>\n<!-- 6 -->\n<g id=\"node8\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 6&#45;&gt;5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>6&#45;&gt;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M243,-36.1686C243,-43.869 243,-53.0257 243,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"239.5001,-61.5867 243,-71.5867 246.5001,-61.5868 239.5001,-61.5867\"/>\n</g>\n<!-- 7 -->\n<g id=\"node9\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 9&#45;&gt;3 -->\n<g id=\"edge6\" class=\"edge\">\n<title>9&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M295.6918,-102.8722C278.6445,-114.237 253.5981,-130.9346 234.4656,-143.6896\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"232.5201,-140.7801 226.1411,-149.2393 236.4031,-146.6044 232.5201,-140.7801\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "union(ds, 7,  3)\n",
        "drawDS(ds)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 271
        },
        "id": "drpB7BVzGNm3",
        "outputId": "6f0f2b32-246f-4374-be55-8a4d070f6f33"
      },
      "execution_count": 25,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7f206e6208d0>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: DisjointSet Pages: 1 -->\n<svg width=\"422pt\" height=\"188pt\"\n viewBox=\"0.00 0.00 422.00 188.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 184)\">\n<title>DisjointSet</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-184 418,-184 418,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 8 -->\n<g id=\"node2\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 0&#45;&gt;8 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M27,-36.1686C27,-43.869 27,-53.0257 27,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"23.5001,-61.5867 27,-71.5867 30.5001,-61.5868 23.5001,-61.5867\"/>\n</g>\n<!-- 1 -->\n<g id=\"node3\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"135\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"135\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 2 -->\n<g id=\"node4\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 3 -->\n<g id=\"node5\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 2&#45;&gt;3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>2&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M120.8705,-100.9353C145.2222,-113.1111 184.762,-132.881 212.2285,-146.6142\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"210.886,-149.8561 221.3955,-151.1978 214.0165,-143.5951 210.886,-149.8561\"/>\n</g>\n<!-- 4 -->\n<g id=\"node6\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 4&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>4&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M186.2693,-105.2693C196.197,-115.197 209.3153,-128.3153 220.4363,-139.4363\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"218.2067,-142.1564 227.7527,-146.7527 223.1564,-137.2067 218.2067,-142.1564\"/>\n</g>\n<!-- 5 -->\n<g id=\"node7\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 5&#45;&gt;3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>5&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M243,-108.1686C243,-115.869 243,-125.0257 243,-133.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"239.5001,-133.5867 243,-143.5867 246.5001,-133.5868 239.5001,-133.5867\"/>\n</g>\n<!-- 6 -->\n<g id=\"node8\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 6&#45;&gt;5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>6&#45;&gt;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M243,-36.1686C243,-43.869 243,-53.0257 243,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"239.5001,-61.5867 243,-71.5867 246.5001,-61.5868 239.5001,-61.5867\"/>\n</g>\n<!-- 7 -->\n<g id=\"node9\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 7&#45;&gt;3 -->\n<g id=\"edge6\" class=\"edge\">\n<title>7&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M299.7307,-105.2693C289.803,-115.197 276.6847,-128.3153 265.5637,-139.4363\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"262.8436,-137.2067 258.2473,-146.7527 267.7933,-142.1564 262.8436,-137.2067\"/>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 9&#45;&gt;3 -->\n<g id=\"edge7\" class=\"edge\">\n<title>9&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M365.1295,-100.9353C340.7778,-113.1111 301.238,-132.881 273.7715,-146.6142\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"271.9835,-143.5951 264.6045,-151.1978 275.114,-149.8561 271.9835,-143.5951\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 25
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "union(ds, 4, 8)\n",
        "drawDS(ds)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 271
        },
        "id": "ib2MbZp-GQiD",
        "outputId": "5fd54b3e-1526-4063-f6e0-a0d4034cf9f3"
      },
      "execution_count": 26,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7f206e5d6cd0>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: DisjointSet Pages: 1 -->\n<svg width=\"422pt\" height=\"188pt\"\n viewBox=\"0.00 0.00 422.00 188.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 184)\">\n<title>DisjointSet</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-184 418,-184 418,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 8 -->\n<g id=\"node2\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 0&#45;&gt;8 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M27,-36.1686C27,-43.869 27,-53.0257 27,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"23.5001,-61.5867 27,-71.5867 30.5001,-61.5868 23.5001,-61.5867\"/>\n</g>\n<!-- 3 -->\n<g id=\"node5\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"207\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"207\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 8&#45;&gt;3 -->\n<g id=\"edge7\" class=\"edge\">\n<title>8&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M48.5278,-101.2234C53.2525,-103.5571 58.2601,-105.9331 63,-108 99.9991,-124.1342 143.5166,-140.0441 172.9513,-150.3683\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"172.1468,-153.7942 182.7416,-153.7783 174.4493,-147.1837 172.1468,-153.7942\"/>\n</g>\n<!-- 1 -->\n<g id=\"node3\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 2 -->\n<g id=\"node4\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 2&#45;&gt;3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>2&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M118.3082,-102.8722C135.3555,-114.237 160.4019,-130.9346 179.5344,-143.6896\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"177.5969,-146.6044 187.8589,-149.2393 181.4799,-140.7801 177.5969,-146.6044\"/>\n</g>\n<!-- 4 -->\n<g id=\"node6\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 4&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>4&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M179.7146,-107.4292C183.9597,-115.9193 189.1536,-126.3071 193.8663,-135.7326\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"190.763,-137.3523 198.3657,-144.7313 197.024,-134.2218 190.763,-137.3523\"/>\n</g>\n<!-- 5 -->\n<g id=\"node7\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 5&#45;&gt;3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>5&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M234.2854,-107.4292C230.0403,-115.9193 224.8464,-126.3071 220.1337,-135.7326\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"216.976,-134.2218 215.6343,-144.7313 223.237,-137.3523 216.976,-134.2218\"/>\n</g>\n<!-- 6 -->\n<g id=\"node8\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 6&#45;&gt;5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>6&#45;&gt;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M243,-36.1686C243,-43.869 243,-53.0257 243,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"239.5001,-61.5867 243,-71.5867 246.5001,-61.5868 239.5001,-61.5867\"/>\n</g>\n<!-- 7 -->\n<g id=\"node9\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 7&#45;&gt;3 -->\n<g id=\"edge6\" class=\"edge\">\n<title>7&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M295.6918,-102.8722C278.6445,-114.237 253.5981,-130.9346 234.4656,-143.6896\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"232.5201,-140.7801 226.1411,-149.2393 236.4031,-146.6044 232.5201,-140.7801\"/>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 9&#45;&gt;3 -->\n<g id=\"edge8\" class=\"edge\">\n<title>9&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M365.4722,-101.2234C360.7475,-103.5571 355.7399,-105.9331 351,-108 314.0009,-124.1342 270.4834,-140.0441 241.0487,-150.3683\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"239.5507,-147.1837 231.2584,-153.7783 241.8532,-153.7942 239.5507,-147.1837\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 26
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "union(ds, 6, 1)\n",
        "drawDS(ds)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 271
        },
        "id": "u3fjUEOZGULq",
        "outputId": "e894defa-6abb-41cb-e21b-473040ee5f9d"
      },
      "execution_count": 27,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7f206e5704d0>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: DisjointSet Pages: 1 -->\n<svg width=\"566pt\" height=\"188pt\"\n viewBox=\"0.00 0.00 566.00 188.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 184)\">\n<title>DisjointSet</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-184 562,-184 562,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 8 -->\n<g id=\"node2\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 0&#45;&gt;8 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M27,-36.1686C27,-43.869 27,-53.0257 27,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"23.5001,-61.5867 27,-71.5867 30.5001,-61.5868 23.5001,-61.5867\"/>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"279\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"279\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 8&#45;&gt;3 -->\n<g id=\"edge8\" class=\"edge\">\n<title>8&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M47.978,-101.4499C52.8229,-103.8225 58.0192,-106.1575 63,-108 124.5871,-130.7826 199.5542,-147.1077 243.0228,-155.5132\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"242.369,-158.9515 252.8468,-157.3813 243.6767,-152.0747 242.369,-158.9515\"/>\n</g>\n<!-- 1 -->\n<g id=\"node3\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 1&#45;&gt;3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>1&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M120.5278,-101.2234C125.2525,-103.5571 130.2601,-105.9331 135,-108 171.9991,-124.1342 215.5166,-140.0441 244.9513,-150.3683\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"244.1468,-153.7942 254.7416,-153.7783 246.4493,-147.1837 244.1468,-153.7942\"/>\n</g>\n<!-- 2 -->\n<g id=\"node5\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 2&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>2&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M190.3082,-102.8722C207.3555,-114.237 232.4019,-130.9346 251.5344,-143.6896\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"249.5969,-146.6044 259.8589,-149.2393 253.4799,-140.7801 249.5969,-146.6044\"/>\n</g>\n<!-- 4 -->\n<g id=\"node6\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 4&#45;&gt;3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>4&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M251.7146,-107.4292C255.9597,-115.9193 261.1536,-126.3071 265.8663,-135.7326\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"262.763,-137.3523 270.3657,-144.7313 269.024,-134.2218 262.763,-137.3523\"/>\n</g>\n<!-- 5 -->\n<g id=\"node7\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 5&#45;&gt;3 -->\n<g id=\"edge5\" class=\"edge\">\n<title>5&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M306.2854,-107.4292C302.0403,-115.9193 296.8464,-126.3071 292.1337,-135.7326\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"288.976,-134.2218 287.6343,-144.7313 295.237,-137.3523 288.976,-134.2218\"/>\n</g>\n<!-- 6 -->\n<g id=\"node8\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 6&#45;&gt;3 -->\n<g id=\"edge6\" class=\"edge\">\n<title>6&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M367.6918,-102.8722C350.6445,-114.237 325.5981,-130.9346 306.4656,-143.6896\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"304.5201,-140.7801 298.1411,-149.2393 308.4031,-146.6044 304.5201,-140.7801\"/>\n</g>\n<!-- 7 -->\n<g id=\"node9\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"459\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"459\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 7&#45;&gt;3 -->\n<g id=\"edge7\" class=\"edge\">\n<title>7&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M437.4722,-101.2234C432.7475,-103.5571 427.7399,-105.9331 423,-108 386.0009,-124.1342 342.4834,-140.0441 313.0487,-150.3683\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"311.5507,-147.1837 303.2584,-153.7783 313.8532,-153.7942 311.5507,-147.1837\"/>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"531\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"531\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 9&#45;&gt;3 -->\n<g id=\"edge9\" class=\"edge\">\n<title>9&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M510.022,-101.4499C505.1771,-103.8225 499.9808,-106.1575 495,-108 433.4129,-130.7826 358.4458,-147.1077 314.9772,-155.5132\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"314.3233,-152.0747 305.1532,-157.3813 315.631,-158.9515 314.3233,-152.0747\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 27
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "find(ds, 0)\n",
        "drawDS(ds)"
      ],
      "metadata": {
        "id": "TgbtSIL_GXp6",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 175
        },
        "outputId": "32d8b4d7-3c99-4494-d11f-b85f600437f5"
      },
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7f206e5bb5d0>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: DisjointSet Pages: 1 -->\n<svg width=\"638pt\" height=\"116pt\"\n viewBox=\"0.00 0.00 638.00 116.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 112)\">\n<title>DisjointSet</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-112 634,-112 634,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 3 -->\n<g id=\"node2\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 0&#45;&gt;3 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M47.9328,-29.5755C52.78,-31.9416 57.9887,-34.2421 63,-36 137.3014,-62.0635 228.5342,-77.8116 278.308,-85.11\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"277.8833,-88.5848 288.2789,-86.5398 278.877,-81.6557 277.8833,-88.5848\"/>\n</g>\n<!-- 1 -->\n<g id=\"node3\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 1&#45;&gt;3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>1&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M120.0435,-29.279C124.885,-31.6605 130.0634,-34.0422 135,-36 184.0676,-55.4591 243.0086,-71.8904 279.7451,-81.3489\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"278.937,-84.7547 289.4913,-83.8285 280.663,-77.9708 278.937,-84.7547\"/>\n</g>\n<!-- 2 -->\n<g id=\"node4\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 2&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>2&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M192.8705,-28.9353C217.2222,-41.1111 256.762,-60.881 284.2285,-74.6142\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"282.886,-77.8561 293.3955,-79.1978 286.0165,-71.5951 282.886,-77.8561\"/>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"243\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"243\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 4&#45;&gt;3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>4&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M258.2693,-33.2693C268.197,-43.197 281.3153,-56.3153 292.4363,-67.4363\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"290.2067,-70.1564 299.7527,-74.7527 295.1564,-65.2067 290.2067,-70.1564\"/>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"315\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"315\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 5&#45;&gt;3 -->\n<g id=\"edge5\" class=\"edge\">\n<title>5&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M315,-36.1686C315,-43.869 315,-53.0257 315,-61.5834\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"311.5001,-61.5867 315,-71.5867 318.5001,-61.5868 311.5001,-61.5867\"/>\n</g>\n<!-- 6 -->\n<g id=\"node7\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"387\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"387\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n</g>\n<!-- 6&#45;&gt;3 -->\n<g id=\"edge6\" class=\"edge\">\n<title>6&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M371.7307,-33.2693C361.803,-43.197 348.6847,-56.3153 337.5637,-67.4363\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"334.8436,-65.2067 330.2473,-74.7527 339.7933,-70.1564 334.8436,-65.2067\"/>\n</g>\n<!-- 7 -->\n<g id=\"node8\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"459\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"459\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n</g>\n<!-- 7&#45;&gt;3 -->\n<g id=\"edge7\" class=\"edge\">\n<title>7&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M437.1295,-28.9353C412.7778,-41.1111 373.238,-60.881 345.7715,-74.6142\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"343.9835,-71.5951 336.6045,-79.1978 347.114,-77.8561 343.9835,-71.5951\"/>\n</g>\n<!-- 8 -->\n<g id=\"node9\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"531\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"531\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n</g>\n<!-- 8&#45;&gt;3 -->\n<g id=\"edge8\" class=\"edge\">\n<title>8&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M509.9565,-29.279C505.115,-31.6605 499.9366,-34.0422 495,-36 445.9324,-55.4591 386.9914,-71.8904 350.2549,-81.3489\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"349.337,-77.9708 340.5087,-83.8285 351.063,-84.7547 349.337,-77.9708\"/>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"603\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"603\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n</g>\n<!-- 9&#45;&gt;3 -->\n<g id=\"edge9\" class=\"edge\">\n<title>9&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M582.0672,-29.5755C577.22,-31.9416 572.0113,-34.2421 567,-36 492.6986,-62.0635 401.4658,-77.8116 351.692,-85.11\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"351.123,-81.6557 341.7211,-86.5398 352.1167,-88.5848 351.123,-81.6557\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {},
          "execution_count": 29
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "ni9Z7JfOl9jG"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}