# Easy C++ Solution 9ms

• Thanks to the samples of @niwota @wzypangpang, the solution has been updated.

The unique redundant edge appears when

1. an edge connect a child with its duplicated father.
2. an edge which makes one and only one cycle in the tree.
3. an edge such that both 1) and 2). (only one redundant edge)

Solution:

1. traverse each edge and record the edge which causes case 1) or 2);
2. if case 1) doesn't occur, return the last input edge which makes a cycle under case 2).
3. return the edge satisfying case 3) if it exists; otherwise, return the edge under case 1).
class Solution {
public:
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int u, v;
bool hasCycle = false;
vector<int> dup_node;  //{child, dup father}
vector<int> ringEdge;
for(const auto &e: edges){
u = e[0]; v = e[1];
//a node has multiple fathers
if(fa.find(v) != fa.end()){
dup_node.push_back(v);
dup_node.push_back(u);
}
else fa[v] = u;
//at most one cycle in the tree
if(!hasCycle){
if(hasCycle = checkCycle(v)){
ringEdge.push_back(u);
ringEdge.push_back(v);
}
}
}
if(dup_node.empty()) return ringEdge;
if(checkCycle(dup_node[0])) return {fa[dup_node[0]], dup_node[0]};
else return {dup_node[1], dup_node[0]};
}
bool checkCycle(int v){
int node = v;
while(fa.find(v) != fa.end()){
v = fa[v];
if(v == node) return true;
}
return false;
}
unordered_map<int, int> fa;
};

• This solution is wrong.
e.g. [[4,2],[1,5],[5,2],[5,3],[2,4]]