[Solution] DFS Trees Codeforces Solution | Solution Codeforces

E. DFS Trees

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a connected undirected graph consisting of n$n$ vertices and m$m$ edges. The weight of the i$i$-th edge is i$i$.

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

        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)

Difference Operations Codeforces Solution

Difference of GCDs Codeforces Solution

Doremy's IQ Codeforces Solution

Difference Array Solution Codeforces 

Partial Virtual Trees Codeforces Solution

DFS Trees Codeforces Solution

    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

The first line of the input contains two integers n$n$, m$m$ (2≤n≤105$2\le n\le {10}^5$, n−1≤m≤2⋅105$n-1\le m\le 2\cdot {10}^5$) — the number of vertices and the number of edges in the graph.

Each of the following m$m$ lines contains two integers ui$u_i$ and vi$v_i$ (1≤ui,vi≤n$1\le u_i,v_i\le n$, ui≠vi$u_i\ne v_i$), describing an undirected edge (ui,vi)$(u_i,v_i)$ in the graph. The i$i$-th edge in the input has weight i$i$.

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

Output

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