# 684. Redundant Connection

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

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., 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 resulting graph is given as a 2D-array of `edges`. Each element of `edges` is a pair `[u, v]` with `u < v`, that represents an **undirected** edge connecting nodes `u` and `v`.

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 given 2D-array. The answer edge `[u, v]` should be in the same format, with `u < v`.

**Example 1:**<br>

```
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
  1
 / \
2 - 3
```

**Example 2:**<br>

```
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
    |   |
    4 - 3
```

**Note:**<br>

The size of the input 2D-array will be between 3 and 1000.

Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

**Update (2017-09-26):**\
We have overhauled the problem description + test cases and specified clearly the graph is an **undirected** graph. For the **directed**graph follow up please see [**Redundant Connection II**](https://leetcode.com/problems/redundant-connection-ii/description/)). We apologize for any inconvenience caused.

```cpp
// DFS
bool hasCycle(int start, int end, unordered_map<int, unordered_set<int> >& graph, int pre) {
    if (graph[start].count(end)) return true;
    for (int node : graph[start]) {
        if (node == pre) continue; // the variable pre is to avoid cycle, e.g. 1->2, then 2->1
        if (hasCycle(node, end, graph, start)) return true;
    }
    return false;
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) { // time: O(n); space: O(n)
    unordered_map<int, unordered_set<int> > graph; // adjacency list
    // Add each edge into the graph and check if there is a cycle
    for (auto& edge : edges) {
        if (hasCycle(edge[0], edge[1], graph, -1)) return edge;
        graph[edge[0]].insert(edge[1]);
        graph[edge[1]].insert(edge[0]);
    }
    return {}; // no redundant edge
}
```

```cpp
// BFS
vector<int> findRedundantConnection(vector<vector<int>>& edges) { // time: O(n); space: O(n)
    unordered_map<int, unordered_set<int> > graph; // adjacency list
    // Add each edge into the graph and check if there is a cycle
    for (auto& edge : edges) {
        queue<int> q({edge[0]});
        unordered_set<int> s({edge[0]});
        while (!q.empty()) {
            auto& t = q.front(); q.pop();
            if (graph[t].count(edge[1])) return edge;
            for (int node : graph[t]) {
                if (s.count(node)) continue;
                q.push(node);
                s.insert(node);
            }
        }
        graph[edge[0]].insert(edge[1]);
        graph[edge[1]].insert(edge[0]);
    }
    return {}; // no redundant edge
}
```

```cpp
// Union Find (Weighted Quick-Union with Path Compression)
int getRoot(vector<int>& root, int i) {
    return root[i] == -1 ? i : root[i] = getRoot(root, root[i]);
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) { // time: O(nlg*(n)); space: O(n)
    vector<int> root(1001, -1), size(1001, 1);
    for (auto& edge : edges) {
        int r1 = getRoot(root, edge[0]), r2 = getRoot(root, edge[1]);
        if (r1 == r2) return edge;
        if (size[r1] < size[r2]) {
            root[r1] = r2;
            size[r2] += size[r1];
        } else {
            root[r2] = r1;
            size[r1] += size[r2];
        }
    }
    return {}; // no redundant edge
}
```

{% content-ref url="261.-graph-valid-tree" %}
[261.-graph-valid-tree](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/graph/261.-graph-valid-tree)
{% endcontent-ref %}

{% content-ref url="685.-redundant-connection-ii" %}
[685.-redundant-connection-ii](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/graph/685.-redundant-connection-ii)
{% endcontent-ref %}