684 - Redundant Connection

#medium

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Example 1:

Input: edges = [ [1,2],[1,3],[2,3] ]
Output: [2,3]

Example 2:

Input: edges = [ [1,2],[2,3],[3,4],[1,4],[1,5] ]
Output: [1,4]

Constraints:

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ai < bi <= edges.length
• ai != bi
• There are no repeated edges.
• The given graph is connected.

class Solution {
public:
    unordered_map<int, int> father; // key,father_key
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        // 把環上的最後一個邊移除 UnionFind(判斷是不是一個group)
        for ( int i = 0; i < edges.size(); i++ ) {
            int a = edges[i][0];
            int b = edges[i][1];
            if ( father.find(a) == father.end() ) father[a] = a;
            if ( father.find(b) == father.end() ) father[b] = b;
            // a,b是不是group，老祖宗同一個嗎
            if ( FindFather(a) == FindFather(b) ) return edges[i];
            else Union( a, b );
        }

        return {};
    }

		// 順便更新此節點的father為老祖宗。
    int FindFather( int x ) {
        int y = x;
        while( father[y] != y ) {
            y = father[y]; 
            father[x] = father[y];
        }

        return father[x];
    }

	  // 聯姻
    void Union( int x, int y ) {
        x = father[x];
        y = father[y];
        if ( x < y ) father[y] = x;
        else father[x] = y;
    }

};