I too Did the Same Thing … , if You find the mistake @loser_3117 . Do Reply
It was a real delight to solve this problem.
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 .
I did the same too . partially correct answer
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.
Here is my simple approach… No dfs bfs traversal, no graph stored just using frequency array… I solved it.
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
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
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
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.
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.
Thanks, I got my mistake.
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.
Did you understand why our solution was wrong ?
Because I am not able to understand.
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
The approach itself is incorrect.
can you please explain in detail
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.