dev/democards/problems/problems/684.redundant-connection.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "In this problem, a tree is an **undirected** graph that is connected and has\n",
    "no cycles.\n",
    "\n",
    "The given input is a graph that started as a tree with N nodes (with distinct\n",
    "values 1, 2, ..., N), with one additional edge added. The added edge has two\n",
    "different vertices chosen from 1 to N, and was not an edge that already\n",
    "existed.\n",
    "\n",
    "The resulting graph is given as a 2D-array of `edges`. Each element of `edges`\n",
    "is a pair `[u, v]` with `u < v`, that represents an **undirected** edge\n",
    "connecting nodes `u` and `v`.\n",
    "\n",
    "Return an edge that can be removed so that the resulting graph is a tree of N\n",
    "nodes. If there are multiple answers, return the answer that occurs last in\n",
    "the given 2D-array. The answer edge `[u, v]` should be in the same format,\n",
    "with `u < v`.\n",
    "\n",
    "**Example 1:**\n",
    "\n",
    "\n",
    "\n",
    "    Input: [[1,2], [1,3], [2,3]]\n",
    "    Output: [2,3]\n",
    "    Explanation: The given undirected graph will be like this:\n",
    "      1\n",
    "     / \\\n",
    "    2 - 3\n",
    "\n",
    "\n",
    "**Example 2:**\n",
    "\n",
    "\n",
    "\n",
    "    Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]\n",
    "    Output: [1,4]\n",
    "    Explanation: The given undirected graph will be like this:\n",
    "    5 - 1 - 2\n",
    "        |   |\n",
    "        4 - 3\n",
    "\n",
    "\n",
    "**Note:**\n",
    "\n",
    "* The size of the input 2D-array will be between 3 and 1000.\n",
    "* Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.\n",
    "\n",
    "\n",
    "\n",
    "**Update (2017-09-26):**\n",
    "We have overhauled the problem description + test cases and specified clearly\n",
    "the graph is an **_undirected_** graph. For the **_directed_** graph follow up\n",
    "please see **[Redundant Connection\n",
    "II](https://leetcode.comhttps://leetcode.com/problems/redundant-connection-ii/description/)** ).\n",
    "We apologize for any inconvenience caused."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "findRedundantConnection (generic function with 1 method)"
     },
     "metadata": {},
     "execution_count": 1
    }
   ],
   "cell_type": "code",
   "source": [
    "# @lc code=start\n",
    "using LeetCode\n",
    "\n",
    "function UFS()\n",
    "    function findRoot(u::Int, farther::Vector{Int})\n",
    "        return (u == farther[u]) ? (u) : (farther[u] = findRoot(farther[u], farther))\n",
    "    end\n",
    "\n",
    "    function merge(u::Int, v::Int, farther::Vector{Int})\n",
    "        u = findRoot(u, farther)\n",
    "        v = findRoot(v, farther)\n",
    "        (u == v) || (farther[u] = v)\n",
    "        nothing\n",
    "    end\n",
    "\n",
    "    function issameRoot(u::Int, v::Int, farther::Vector{Int})\n",
    "        return findRoot(u, farther) == findRoot(v, farther)\n",
    "    end\n",
    "\n",
    "    findRoot, merge, issameRoot\n",
    "end\n",
    "\n",
    "function findRedundantConnection(edges::Vector{Vector{Int}})::Vector{Int}\n",
    "    farther = collect(1:1000)\n",
    "    findRoot, merge, issameRoot = UFS()\n",
    "    for edge in edges\n",
    "        if issameRoot(edge..., farther)\n",
    "            return edge\n",
    "        end\n",
    "        merge(edge..., farther)\n",
    "    end\n",
    "end\n",
    "# @lc code=end"
   ],
   "metadata": {},
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
   ],
   "metadata": {}
  }
 ],
 "nbformat_minor": 3,
 "metadata": {
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.1"
  },
  "kernelspec": {
   "name": "julia-1.10",
   "display_name": "Julia 1.10.1",
   "language": "julia"
  }
 },
 "nbformat": 4
}