# Why does this(Input: [[2,3],[5,2],[1,5],[4,2],[4,1]] Output: [4,2] Expected: [4,1] ) happens?

@contributors
As the title says, my solution is not accepted. Why does this happen? I think we should remove [4,2] as my solution. What is wrong?

Input: [[2,3],[5,2],[1,5],[4,2],[4,1]]
Output: [4,2]
Expected: [4,1]

``````class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
map<int, int> parent;
for (auto e : edges) {
if (parent.find(e[1]) != parent.end()) {
return e;
}
if (parent.find(e[0]) != parent.end()) {
if (parent[e[0]] == e[1])
return e;
}
parent[e[1]] = e[0];
}
set<int> root;
for (auto e : edges) {
if (root.find(e[1]) != root.end())
return e;
root.insert(e[0]);
}
return edges.back();
}
};
``````

• Because 4,1 is the last edge that forms a cycle.

• @wavy But is that ok if the Node(2) has 2 father Node(5) and Node(4)? thx

• @wavy
But the node 2 has two parent node, thus 5 and 4. Is this a tree if we do not remove [4, 2]?

• @yanchao_hust I too have exactly the same question!

• I think I just assumed it's not a rooted tree

• @yanchao_hust Funny thing is OJ can not solve this test case [[3,1],[2,1]]...So obviously, they assume this is an undirected graph.

• Same problem, the statement of the puzzle says clearly [u, v] means v is the child of u, then [4, 2] should be returned, not [4, 1]

• So obviously, they assume this is an undirected graph

But then the words "child" and "parent" must not have been used. Am I wrong?

• @zhangsikai123
I think so. But it really makes me think it is a rooted tree.

• So obviously, they assume this is an undirected graph

But then the words "child" and "parent" must not have been used. Am I wrong?

Also, if it is undirected graph, then cycles are not redundant any more. Cycles are only redundant if it is tree.

• @thalaiva

Do not mind. Of course, they made a mistake.

• The same problem with the test input:
[[5,2],[3,4],[4,3],[5,3],[1,3]]

there are three parents for node.val = 3,
so there are more than one edge required to be removed.

Wiki - Tree (data structure)

• @bethoven I don't quite understand what do you mean, but obviously, the definition of a tree (in graph theory)(https://en.wikipedia.org/wiki/Tree_(graph_theory)), is 'an undirected graph with no cycle'.

• @zhangsikai123
But they gave parent-child relationship...it is not undirected...

• This post is deleted!

• This post is deleted!

• my code failed as this test too. Seems wrong test case.

• @cygnus wrong test case.

• @realhly88 Sure, the problem set is definitely misleading, just think if we knew this definition we might figured they made a mistake and solved the stupid question.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.