CONGRAPH - Connected country
After a strong earthquake many roads of the ancient country GRAPH were destroyed. The country is divided into disconnected areas so that from one area city it is impossible to reach another area city. Pharaoh wants to restore the road infrastructure and connect all the cities. He asks the great Thoth to find the minimum number of roads needed for this.
Input
The first line of input will contain two space separated integer numbers: 0 < N ≤ 800000, number of cities and 0 < M < 4000000, number of roads. Follow M lines. Each line represents cities (numbering is zero based) connected by road. All roads are bidirectional.
Output
One integer number. Answer of the Thoth
Example
Input: 6 6 0 1 0 2 1 2 3 4 3 5 4 5 Output: 1
Explanation
One road from the city number 1 to the city number 4 makes GRAPH connected.
hide comments
|
h3r37ic_m46607:
2024-06-18 00:07:36
Python is never going to cut this in 10s. I implemented UnionFind data structure, with one-pass path halving find method, and union by rank method. I used numpy arrays, sys.stdin.read, sys.stdout.write, and every little dumb adjustment that makes your code actually worse, but faster, and I was still getting TLE. Then I dropped numpy and went with the lists, and the code passed with PyPt 3.6 jit compiler. But not with the common Python 3.9, because it just isn't cut out for speed. Obviously the judge is not that well optimized for different programming languages. |
|
Jean-Ralph Aviles:
2021-08-23 22:46:05
TLE! Could only get mine to pass with an O(m * log(n)) solution. Last edit: 2021-08-24 08:02:26 |
|
shikhar_may7:
2020-05-03 23:35:00
In the case of DSU, Balance the tree when taking Union else it will result in TLE! |
|
y17prashant:
2019-11-01 03:28:52
DSU is working fine |
|
medhruv7:
2019-08-29 08:11:09
My Dsu not working here , got AC with dfs , plz help |
| Added by: | julkas |
| Date: | 2018-05-21 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
RSS