|
|
good problem. dynacon!
To avoid TLE:
Use dynamic array instead of linked list for better locality.
Break early when a first spanning tree is found. (important).
Edited by author 12.01.2025 23:51 input:
5 5
1 2 0
2 3 1
2 4 1
3 4 1
4 5 2
one possible output:
1 2 3 5
wrong output:
1 2 3 4 5
Don't forget that the output also needs to have as few edges as possible! Obviously, size of answer is always n-1 One way I can think of is to sort edge by cost
and use dynamic connectivity
But it's very hard to implement :(
What's the better solution? divide and conquer is ok. but i can't understand now .And i get T with dynamic connectivity. One way I can think of is to sort edge by cost
and use dynamic connectivity
But it's very hard to implement :(
What's the better solution? Lucky one, I have TL with this method. |
|
|
