DFS Trees
Contest: Codeforces Round 808 (Div. 1)
Difficulty rating: 2400
Tags: dfs and similar, dsu, graphs, greedy, sortings, trees

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

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

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 format:
The first line of the input contains two integers $$$n$$$, $$$m$$$ ($$$2\le n\le 10^5$$$, $$$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$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1\le u_i, v_i\le n$$$, $$$u_i\ne v_i$$$), describing an undirected edge $$$(u_i,v_i)$$$ in the graph. The $$$i$$$-th edge in the input has weight $$$i$$$.

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

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Here is the graph given in the first example.

There is only one minimum spanning tree in this graph. A minimum spanning tree is $$$(1,2),(3,5),(1,3),(2,4)$$$ which has weight $$$1+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)$$$;
- add edge $$$(1,2)$$$ into the edge set s, calling dfs(2):   vis[2] := true  iterate through each edge $$$(2,1),(2,3),(2,4)$$$;  because vis[1] = true, ignore the edge $$$(2,1)$$$;  add edge $$$(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)$$$ with total weight $$$1+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.

Example input:
5 5
1 2
3 5
1 3
3 2
4 2

Example output:
01111

Example input:
10 11
1 2
2 5
3 4
4 2
8 1
4 5
10 5
9 5
8 2
5 7
4 6

Example output:
0011111011

Editorial:
Minimum spanning tree is unique in the given graph.
If $$$\operatorname{findMST}$$$(x) creates an MST, there is no cross edge in the graph. So if you can determine whether there is a cross edge starting DFS from every node, the problem is solved.
Pay attention to every edge that is not in the MST. Let's focus on one single edge $$$(u,v)$$$ and see starting DFS from which node, $$$(u,v)$$$ is a cross edge. Take the following graph as an example.

If we start from nodes $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$, $$$e$$$ or $$$f$$$, $$$(u,v)$$$ is a cross edge. If we start from nodes $$$t$$$, $$$u$$$, $$$o$$$ or $$$v$$$, $$$(u,v)$$$ is not a cross edge. We can find that when considering $$$u$$$ as the root of the tree, $$$o$$$ and $$$v$$$ are on the subtree of $$$v$$$. When considering $$$v$$$ as the root of the tree, $$$t$$$ and $$$u$$$ are on the subtree of $$$u$$$.
So if an edge $$$(u,v)$$$ is not in the MST, only the subtree of $$$u$$$($$$u$$$ included, when considering $$$v$$$ as the root) and the subtree of $$$v$$$($$$v$$$ included, when considering $$$u$$$ as the root) can be answers. We just need to do this process for each edge not in the MST. After that we can get the answers.
We can finish the process in $$$O(n\log n)$$$ with bin-up on tree and BIT or in $$$O(n)$$$ with some case work while dfs.