Minimum spanning tree 2 - MarisaOJ: Marisa Online Judge

Given a connected, weighted, undirected graph of

$n$ vertices and

$m$ edges. For every edge, determine if it belongs to at least one minimum spanning tree. ### Input - The first line contain 2 integers

$n, m$ . - The next

$m$ lines, each line contains 3 integers

$u, v, w$ , there is an edge weigh

$w$ between

$u$ and

$v$ . ### Output - Print a binary string of length

$m$ . If

$i^{th}$ edge belongs to at least one minimum spanning tree, the

$i^{th}$ character should be

$1$ , otherwise

$0$ . ### Constraints -

$1 \le n, m \le 10^5$ . -

$1 \le u, v \le n$ . -

$1 \le w \le 10^9$ ### Example Input:

$4 7 1 2 2 2 3 2 4 1 1 3 2 5 1 4 4 1 2 1 4 2 3$

Output:

$0110010$

Topic

Greedy

DSU

Rating

1600

Solution (0)

Solution