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!

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?