ROOTTREE - Editorial

editorial
, , , ,
21

I too Did the Same Thing … , if You find the mistake @loser_3117 . Do Reply

22

It was a real delight to solve this problem.

23

Firstly, your solution will most probably exceed the time limit as the solution that you have described is of O(n^2) time complexity.

Secondly, consider this test case:

1
7
1 2
2 3
3 4
5 4
6 5
7 6

(u -> v) represent directed edge from u to v
(u <- v) represent directed edge from v to u

1 -> 2 -> 3 -> 4 <- 5 <- 6 <- 7

The ans to the above case is 1. One of the ways can be that we remove the edge between 4 and 5 and add an edge from 5 to 1, then 7 will be the root .

But your solution will provide a different answer. So you can see the error for yourself.

Hope you find this helpful :smile:.

7 Likes
24

I guess you are not alone. Here is mine solution : CodeChef: Practical coding for everyone

1 Like
25

I did the same too . partially correct answer :sob:

26

@dgupta0812 Thanks a lot bro for the example.

1 Like
27

Thanks bro, i assumed fliping an edge will give same effect as removing an edge and rejoining it with other, but solution is of O(n) ,did two dfs only.

28

Here is my simple approach… No dfs bfs traversal, no graph stored just using frequency array… I solved it.

CodeChef: Practical coding for everyoneSolution

29

Just store Indegree of each node and subtract 1 from each node value and that will be the answer.
https://www.codechef.com/viewsolution/38221498
This approach works because any node can’t have more than 1 incoming edges in order to be directed tree. So all such edges will be flipped and added to the answer

31

try this test case ,answer should be 2
1
12
1 2
2 3
8 7
7 6
6 5
5 3
12 11
11 10
10 9
9 4
4 3

32

Yeah, that’s the solution. But I don’t know why my code fails. A test case would be helpful.
https://www.codechef.com/viewsolution/38234291

33

Very nice question To solve this You can alternatively find no of nodes with 0 indegree (i.e no of roots)
and then subtract this number by one.

34

Try with this test case
1
7
1 2
3 2
4 2
5 1
6 5
7 5
Ans should be 3.
Try to analyze by dividing graph into smaller sub graph.

1 Like
35

Thanks, I got my mistake.

1 Like
36

Another way might be calculating the no. of connected components and substract it by 1.
construct the graph from start and at the each time of adding new edge, check whether it increases or decreases (or no effect on) the number of connected components.

Code:

38

Did you understand why our solution was wrong ?
Because I am not able to understand.

39

for _ in range(int(input())):
n=int(input())
r=[]
for i in range(n-1):
a,b=map(int,input().split())
r.append(b)
print(len®-len(set®))

This worked!!
just counting edges whose indeg > 1 and deleting

1 Like
40

The approach itself is incorrect.

1 Like
41

can you please explain in detail

42

The in-degree summation of all vertices should be n-1. We need to distribute it, so that root has zero in-degree, while all others are 1. Therefore, just check number of vertices with zero in-degree, say cnt. We just need one of them to have in-degree zero, therefore, answer is cnt-1.

2 Likes