Disjoint Set Test

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 1.4s

Memory limit: 256M

Problem types

Xyene is doing a contest. He comes across the following problem:

You have a weighted graph of $N$ $N$ $(1 \le N \le 100\,000)$ $(1 \leq N \leq 100 000)$ vertices labelled from $1$ $1$ to $N$ $N$ and $M$ $M$ $(1 \le M \le 1\,000\,000)$ $(1 \leq M \leq 1 000 000)$ edges labelled from $1$ $1$ to $M$ $M$ . Each edge has a unique positive weight — specifically, an edge that shows up earlier in the input has a strictly less weight than an edge that shows up later in the input. The graph will not have multiple edges or self loops. From this information, determine the edges in the minimum spanning tree, or that one does not exist. The minimum spanning tree of this graph is guaranteed to be unique if it exists.

Xyene knows that one fast solution uses Kruskal's algorithm with a Disjoint Set data structure. He practices that data structure every day, but still somehow manages to get it wrong. Will you show him a working example?

Xyene recalls that Kruskal's algorithm goes through all the edges one by one sorted by nondecreasing edge weight. An edge will be added to the minimum spanning tree if the two vertices it connects were not connected by any path so far.

Input Specification

The first line has $N$ $N$ and $M$ $M$ .

The $i+1$ $i + 1$ -th line has $u_i$ $u_{i}$ and $v_i$ $v_{i}$ , the two vertices that the $i$ $i$ -th edge connects.

Output Specification

If no minimum spanning tree exists, output Disconnected Graph.

Otherwise, output $N-1$ $N - 1$ lines: the numbers of the edges that are in the minimum spanning tree in any order.

Sample Input 1

Copy

Sample Output 1

Copy

1
2
4

Sample Input 2

Copy

3 1
1 2

Sample Output 2

Copy

Disconnected Graph

Comments

-6

31501357 commented on Dec. 1, 2019, 6:35 p.m.

Prim's algorithm works here too. Fast input is recommended though.

This comment is hidden due to too much negative feedback. Show it anyway.

-23
mindplaysgaming commented on Aug. 14, 2019, 5:47 p.m. ← edited →
Copy
Scanner sc=new Scanner(System.in); System.out.println("Xyene, Do the question yourself!");
This comment is hidden due to too much negative feedback. Show it anyway.

27

OneYearOld commented on July 28, 2020, 7:42 p.m.

https://dmoj.ca/problem/ds2/submissions/Xyene/

He did

-14

NT_AUTHORITY_SYSTEM commented on June 8, 2018, 10:34 p.m. ← edited →

Only 10 points for a link cut tree?

Edit: never mind, apparently disjoint sets are also a data structure.

This comment is hidden due to too much negative feedback. Show it anyway.

1

31501357 commented on June 24, 2019, 3:08 a.m.

Well to make logarithmic time TLE would require massive amount of input. So there really isn't a good way of penalizing people for using link-cut trees.

6

Plasmatic commented on June 24, 2019, 6:48 p.m. ← edit 2 →

Some simple disjoint set implementations (i.e. Only using union-by-rank optimization) take $\mathcal{O}(\log N)$ $O (\log N)$ time per operation

edit: Google Code Jam's problem preparation guide also heavily discourages against trying to differentiate between $\mathcal{O}(N)$ $O (N)$ and $\mathcal{O}(N \log N)$ $O (N \log N)$ in problems

13

wleung_bvg commented on June 8, 2018, 11:40 p.m.

Well that's certainly one way to solve it, but not the only way (or the intended way).