Batman And Graphs
Batman likes Gotham a lot. He likes it because in this city, it is possible to travel from any junction to any other junction using the roads of the city. Also, all the roads are Bidirectional. However, Joker plans to disrupt the city. He asks Batman to assign direction to every road of the city i.e. assigning a direction so that the roads become unidirectional in such a way that it's still possible to travel from every junction to every other junction of the city using the unidirectional roads.. You have to tell the minimum cost of the roads that Batman has to add so that after assigning directions to all the roads (old + new), he can travel from every junction to every other junction. Cost of adding a new road between two junctions is 1500$
- First line contains T, the number of test cases.
- The first line of each test case contains two integers N, M , total junctions and total roads respectively
- The following M lines contains two integers a, b denoting a bidirectional road between junction a and b. Also, 1 ≤ a,b ≤ N
- There will not be a road from a junction to itself.
- A bidirectional road between junction a & b is not given more than once.
Output the minimum cost of adding roads to the city
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 105
- 1 ≤ M ≤ 5*105
The summation of N,M over all test cases is ≤ 106
Input: 2 4 4 1 2 2 3 3 4 4 1 2 1 1 2 Output: 0 1500
We can assign direction 1 -> 2, 2 -> 3, 3 -> 4, 4 -> 1, so no need to add extra roads, so cost is zero.
In the second examples we can assign direction 1 -> 2 to our initial road and then we have to add an extra road in direction 2 -> 1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions