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:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
1
/ \
2 - 3
Example 2:
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:
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 directedgraph follow up please see Redundant Connection II). We apologize for any inconvenience caused.
// 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
}
// 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
}
// 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
}