ROOTTREE - Editorial

editorial
, , , ,
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
43

Hi, can you explain the logic. I looked at your code but didn’t completely understand what’s happening. What do you mean by connected components in a directed graph?

44

I have a solution of this problem, please correct me if I am wrong.

we can count the minimum number of connected sub-trees in this initially given directed tree.

let the count be n, so the answer will be n - 1.

please correct me if I am wrong

Thank you!

45

Can anyone explain what is wrong in this approach?
Find all the connected components and then return no. of connected components -1