All submissions for this problem are available.
Well ism to iit conversion was not at all an easy task and many college students had given huge amount of time and energy in it. Well once Shashank Sir and Varun Sir were going to Delhi for one of their regular meetings with the politicians. Since the journey was long and varun sir being a batman fanatic, always imagined a self made story for batman. So he told shashank sir (the amazon guy) the story and asked him to how bane will solve that problem in his imaginative story. The story is as follows.
The city of gotham was constructed keeping in mind that all the colonies in it are well connected. However, over the time as the city administration changed, more and more corrupt officals came into the administration and road maintenance was neglected and done only in a way such that all the colonies remain connected and the sum of all the maintenance costs of these roads is minimum (all roads are of equal length but maintenance costs are different).
Eg ==> if the city has 4 colonies which are connected by the maintained paths and 1 ,2 , 3 and 4 are these colonies ; then there are in total 6 paths that exist.
(1-2 , 1-3 , 1-4 , 2-3 , 2-4 , 3-4) , where 1-2 denotes the path between 1 and 2.
Now Bane is planning to attack the city. But he has very less number of soldiers. Therefore, he needs to find out the decreasing order of busy-ness of all the colonies. Busy-ness of a node is defined as the number of paths in which it is an intermediate colony ( not a start or end node). You can assume that only maintained paths exist.
Now given the initial map of the city (when the city was constructed , that is , with all the roads present). Find the output as given in the statement.
Since shashank sir got busy with his Amazon telephonic interview therefore he asked you to solve the problem.
N = number of colonies of gotham.
R = number of roads that were initially constructed.
The first line of input consists of number N and R .
Next line consists of R triplets each i , j , k denoting that a road exists (or rather existed) between colonies i and j, and k being the maintenance cost of the roads.
Output the decreasing order of the busy-ness of the colonies , one in each line. if two colonies have same busy-ness than output the smaller number colony first.
1 <= N <= 2*10^5
1 <= R <= 10^7
1 <= i , j <= N
WARNING :- LARGE TEST DATA . USE FASTER INPUT / OUTPUT METHODS . EG - scanf() , printf() FOR C , C++
1 2 10
2 3 15
1 3 5
4 2 2
4 3 40
|Tags||dfs, graph, mst, recursion, surajjumpy|
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2|
Fetching successful submissions
If you are still having problems, see a sample solution here.