08-graph.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 그래프"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 서로소(disjoint set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5, 6]\n",
      "[0, 1, 1, 2, 1, 5, 5]\n",
      "1 1 1 1 5 5 \n",
      "[0, 1, 1, 1, 1, 5, 5]\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "v = 6\n",
    "e = 4\n",
    "edge = [\n",
    "  [1,4],\n",
    "  [2,3],\n",
    "  [2,4],\n",
    "  [5,6]\n",
    "]\n",
    "def find_parent(parent, x):\n",
    "  if parent[x] != x:\n",
    "    parent[x] = find_parent(parent, parent[x])\n",
    "  return parent[x]\n",
    "\n",
    "def union_parent(parent, a, b):\n",
    "  a = find_parent(parent, a)\n",
    "  b = find_parent(parent, b)\n",
    "  if a < b:\n",
    "    parent[b] = a\n",
    "  else:\n",
    "    parent[a] = b\n",
    "\n",
    "\n",
    "\n",
    "parent = [0]*(v+1)\n",
    "\n",
    "for i in range(1, v+1):\n",
    "  parent[i] = i\n",
    "\n",
    "print(parent)\n",
    "\n",
    "cycle = False # NOTE\n",
    "for a, b in edge:\n",
    "  if find_parent(parent,a) == find_parent(parent,b): # NOTE\n",
    "    cycle = True\n",
    "    break\n",
    "  else:\n",
    "    union_parent(parent, a, b)\n",
    "\n",
    "print(parent)\n",
    "\n",
    "for i in range(1, v+1):\n",
    "  print(find_parent(parent, i), end=' ')\n",
    "print('')\n",
    "print(parent)\n",
    "\n",
    "print(cycle)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 신장트리"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "v = 6\n",
    "e = 4\n",
    "edge = [\n",
    "  [1,2,29],\n",
    "  [1,5,75],\n",
    "  [2,3,35],\n",
    "  [2,6,34],\n",
    "  [3,4,7],\n",
    "  [4,6,23],\n",
    "  [4,7,13],\n",
    "  [5,6,53],\n",
    "  [6,7,25]\n",
    "]\n",
    "def find_parent(parent, x):\n",
    "  if parent[x] != x:\n",
    "    parent[x] = find_parent(parent, parent[x])\n",
    "  return parent[x]\n",
    "\n",
    "def union_parent(parent, a, b):\n",
    "  a = find_parent(parent, a)\n",
    "  b = find_parent(parent, b)\n",
    "  if a < b:\n",
    "    parent[b] = a\n",
    "  else:\n",
    "    parent[a] = b\n",
    "\n",
    "\n",
    "\n",
    "parent = [0]*(v+1)\n",
    "\n",
    "for i in range(1, v+1):\n",
    "  parent[i] = i\n",
    "\n",
    "edges = []\n",
    "for a,b,cost in edge:\n",
    "  edges.append((cost,a,b))\n",
    "\n",
    "\n",
    "\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 위상정렬"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 연습문제"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 실전문제"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "45d80257ccf4ae77bb116447a323b4ded5c7d4f4eb3ea993cf039511269910c8"
  },
  "kernelspec": {
   "display_name": "Python 3.8.8 ('base')",
   "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.8.8"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}