Codeforces div 3 c

https://codeforces.com/problemset/problem/1167/C

how are we reducing the number of edges in the graph without changing the component?

The problem says that if the news is with ith person then with how many he can spread it. He can spread the message to as many which are connected with him or his friends and all these will be in same connected component.

To solve this problem, build graph from the given input, like for this input

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

these are bidirectional edges

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

In simple way, these are these the the friends relation.

2 - 5
2 - 4
5 - 4
2 - 1
6 - 7
make bidirected graph and using dfs you can solve this.

Here is my solution: https://codeforces.com/contest/1167/submission/87067456

1 Like

Thanks for the detailed explanation but I want the know in the editorial it is written that in the worst case we will have o(n^2) edges so we are trying to reduce the no of edges how are we doing that?
how are we reducing edges?

Let us say that we have a group 5 persons 1 2 3 4 5 then we will have 20 edges. Right?
And in the above edges which I am picking it only contains edges like 1<->2 , 2<->3, 3<->4, 4<->5 edges which is only 10 here and we are not adding edges 1<->3 as if 1 is connected to 2 and 2 is connected to 3 ( Transitivity ) then anyway we have path from 1 to 3 so why to add another edge.

This is how we are reducing edges. ( May be this is what they are talking in the editorial )

Request: From your next doubt do mention that where is your doubt, i.e. editorial, problem understanding, etc.

1 Like

Here is my soln: https://codeforces.com/contest/1167/submission/87075580
this is a disjoint dataset problem and can be solved by union find method.
Simplifications of problem…

  1. make groups of friends that share news.
  2. print the size of group if the member present in that group
1 Like

Thank you!