leetCode: 0684. 冗余连接 [medium]

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

class _684 {

    /**
     * @param Integer[][] $edges
     * @return Integer[]
     */
    public function findRedundantConnection($edges) {
        $root = [];
        $result = [];
        foreach ($edges as $edge) {
            if (empty($root[$edge[1]])) $root[$edge[1]] = $edge[1];
            if (empty($root[$edge[0]])) $root[$edge[0]] = $edge[0];

            $xNode = $this -> findRoot($edge[0], $root);
            $yNode = $this -> findRoot($edge[1], $root);

            if ($xNode === $yNode) $result = $edge;
            $this -> union($edge, $root);
        }

        return $result;
    }


    // lastNode -> parentNode 查找当前节点父节点，如果没有则为自身
    protected function findRoot($value, &$root) {
        while ($value != $root[$value]) $value = $root[$value];
        return $root[$value];
    }


    // 合并相同集合节点， 1 -> 2/3 = 2 -> 1
    protected function union($edge, &$root) {

        $xNode = $this -> findRoot($edge[0], $root);
        $yNode = $this -> findRoot($edge[1], $root);

        if ($xNode !== $yNode) $root[$yNode] = $xNode;
    }

}