The test cases obviously don't follow the problem statement.
check this, is this really a tree even after the [4,3] is deleted?
Request to remove the point of this problem from contest.
@administrators
@contributors
Problem is wrong. Check is test case, it is obviously not a tree even after the edge is deleted.


@StefanPochmann Because 3 is the child of 5 and it is also the child of 1. This is not a tree.


I had the same problem! But apparently, "tree" can also mean just "acyclic connected graph", and the kind of graph that has only one parent per node (which is what I've always called a tree!) is actually a "rooted tree" (https://en.wikipedia.org/wiki/Tree_(graph_theory)#Rooted_tree)

@shell32 Ah, ok. I hadn't noticed it said "child". So I thought it's just a tree, not a rooted tree.

@jiayi.zhang1993
The definition is asking a tree with parents, childs well defined.But it turned out to be remove an edge in an undirected graph to make it a tree.
All the accepted answers are wrong technically.

@realhly88 said in Problem is wrong. Check is test case, it is obviously not a tree even after the edge is deleted.:
All the accepted answers are wrong technically.
Can you show a valid test case which they fail?

@StefanPochmann I think if this is not a rooted tree, there are no conceptions of "child" and "parent".

@realhly88 That's not a valid test case, though, since the problem tells us that we can do it, that there is an answer.

@jiayi.zhang1993 it is exactly the point, the test cases assume an undirected graph which would require union find set, but the problem description assumes directed graph which would require topological sort... and I wasted half an hour programming the latter...

@StefanPochmann what if child node means not a 'direct child node', just 'one of child node in it's subtree' ?

@jiayi.zhang1993 Absolutely, but the problem statement says [a,b] means b is the child of a, which is confusing

@tangalai said in Problem is wrong. Check is test case, it is obviously not a tree even after the edge is deleted.:
@StefanPochmann what if child node means not a 'direct child node', just 'one of child node in it's subtree' ?
That's not a "child" but a "descendant":
https://en.wikipedia.org/wiki/Tree_(data_structure)#Terminology_used_in_trees