# LeetCode 684. Redundant Connection

https://leetcode.com/problems/redundant-connection/description/

## 題目大意

給定無向圖，拔掉一邊使得圖變成樹 (原圖 `n` 個節點、`n` 條邊且無 loop，樹的話應該只會有 `n-1` 條邊)
回傳要拔掉哪條邊，如果答案很多種，依題目輸入邊的順序回傳最後面的那條邊

## 思考

樹不能有 cycle ，所以找出圖中的 cycle 依照輸入順序拔掉最後輸入的那條邊即可

你可以使用 DFS or BFS 來找 cycle ，或者這題我們可以用 disjoint set 來幫忙：
想法就是 cycle 會繞一圈嘛，那麼當我們執行 union 時就會遇到兩點已經屬於同個 set 的情況

我們視 disjoint set 的 union 跟 find 都是 $O(1)$ 的話
使用 DFS (or BFS) 時間複雜度為 $O(n^2)$ ($\forall (u, v)\in E$, using DFS (or BFS) to check whether $u$ and $v$ are connected takes $O(n)$)；使用 disjoint set 的方法時間複雜度只有 $O(n)$

### C++ 參考解答

class DisjointSet
{
public:
    DisjointSet(size_t n) : parent(n), rank(n)
    {
        iota(parent.begin(), parent.end(), 0);
    }

    bool unionSet(int x, int y)
    {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY)
            return false;

        if (rank[rootX] > rank[rootY])
            swap(rootX, rootY);
        parent[rootX] = rootY;
        if (rank[rootX] == rank[rootY])
            ++rank[rootX];
        return true;
    }

    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }

private:
    vector<int> parent;
    vector<int> rank;
};

class Solution
{
public:
    vector<int> findRedundantConnection(vector<vector<int>> &edges)
    {
        DisjointSet uf(edges.size() + 1);

        for (const auto &edge : edges)
        {
            const int u = edge[0];
            const int v = edge[1];
            if (!uf.unionSet(u, v))
                return edge;
        }

        throw;
    }
};

### Go 參考解答

func findRedundantConnection(edges [][]int) []int {
	n := len(edges)
	parent := make([]int, n+1)
	rank := make([]int, n+1)

	for i := 1; i <= n; i++ {
		parent[i] = i
		rank[i] = 1
	}

	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}

	union := func(x, y int) bool {
		rootX, rootY := find(x), find(y)
		if rootX == rootY {
			return false
		}
		if rank[rootX] > rank[rootY] {
			parent[rootY] = rootX
		} else if rank[rootX] < rank[rootY] {
			parent[rootX] = rootY
		} else {
			parent[rootX] = rootY
			rank[rootX]++
		}
		return true
	}

	for _, edge := range edges {
		if !union(edge[0], edge[1]) {
			return edge
		}
	}

	return nil
}