DFS Trees Solution Codeforces

Table of Contents

DFS Trees Solution Codeforces

You are given a connected undirected graph consisting of nn vertices and mm edges. The weight of the ii-th edge is ii.

Here is a wrong algorithm of finding a minimum spanning tree (MST) of a graph:

vis := an array of length n
s := a set of edges

function dfs(u):
    vis[u] := true
    iterate through each edge (u, v) in the order from smallest to largest edge weight
        if vis[v] = false
            add edge (u, v) into the set (s)
            dfs(v)

function findMST(u):
    reset all elements of (vis) to false
    reset the edge set (s) to empty
    dfs(u)
    return the edge set (s)

Each of the calls findMST(1)findMST(2), …, findMST(n) gives you a spanning tree of the graph. Determine which of these trees are minimum spanning trees.

Input DFS Trees Solution Codeforces

The first line of the input contains two integers nnmm (2n1052≤n≤105n1m2105n−1≤m≤2⋅105) — the number of vertices and the number of edges in the graph.

Each of the following mm lines contains two integers uiui and vivi (1ui,vin1≤ui,vi≤nuiviui≠vi), describing an undirected edge (ui,vi)(ui,vi) in the graph. The ii-th edge in the input has weight ii.

It is guaranteed that the graph is connected and there is at most one edge between any pair of vertices.

Output DFS Trees Solution Codeforces

You need to output a binary string ss, where si=1si=1 if findMST(i) creates an MST, and si=0si=0 otherwise.

Examples
input

Copy
5 5
1 2
3 5
1 3
3 2
4 2
output

Copy
01111
input

Copy
10 11
1 2
2 5
3 4
4 2
8 1
4 5
10 5
9 5
8 2
5 7
4 6
output

Copy
0011111011

Note DFS Trees Solution Codeforces

Here is the graph given in the first example.

DFS Trees Solution Codeforces
There is only one minimum spanning tree in this graph. A minimum spanning tree is (1,2),(3,5),(1,3),(2,4)(1,2),(3,5),(1,3),(2,4) which has weight 1+2+3+5=111+2+3+5=11.

Here is a part of the process of calling findMST(1):

  • reset the array vis and the edge set s;
  • calling dfs(1);
  • vis[1] := true;
  • iterate through each edge (1,2),(1,3)(1,2),(1,3);
  • add edge (1,2)(1,2) into the edge set s, calling dfs(2):
    • vis[2] := true
    • iterate through each edge (2,1),(2,3),(2,4)(2,1),(2,3),(2,4);
    • because vis[1] = true, ignore the edge (2,1)(2,1);
    • add edge (2,3)(2,3) into the edge set s, calling dfs(3):

In the end, it will select edges (1,2),(2,3),(3,5),(2,4)(1,2),(2,3),(3,5),(2,4) with total weight 1+4+2+5=12>111+4+2+5=12>11, so findMST(1) does not find a minimum spanning tree.

It can be shown that the other trees are all MSTs, so the answer is 01111.

 

For Solution

Click Here

Leave a Comment