309616: CF1707C. DFS Trees
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
DFS Trees
题意翻译
## 题目描述 有一图有$n$个点$m$条边。第$i$条边的权值是$i$ 现在有一个错误的最小生成树算法（就是有bug） ``` vis := an array of length n s := a set of edges function dfs(u): vis := 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) ``` 每次调用$findMST(i)$时，会返回这个图的最小生成树，你要判定那些是正确的最小生成树题目描述
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](https://en.wikipedia.org/wiki/Minimum_spanning_tree) (MST) of a graph: ``` <pre class="verbatim"><br></br>vis := an array of length n<br></br>s := a set of edges<br></br><br></br>function dfs(u):<br></br> vis := true<br></br> iterate through each edge (u, v) in the order from smallest to largest edge weight<br></br> if vis[v] = false<br></br> add edge (u, v) into the set (s)<br></br> dfs(v)<br></br><br></br>function findMST(u):<br></br> reset all elements of (vis) to false<br></br> reset the edge set (s) to empty<br></br> dfs(u)<br></br> return the edge set (s)<br></br> ``` 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.输入输出格式
输入格式
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.
输出格式
You need to output a binary string $ s $ , where $ s_i=1 $ if findMST(i) creates an MST, and $ s_i = 0 $ otherwise.
输入输出样例
输入样例 #1
5 5
1 2
3 5
1 3
3 2
4 2输出样例 #1
01111输入样例 #2
10 11
1 2
2 5
3 4
4 2
8 1
4 5
10 5
9 5
8 2
5 7
4 6输出样例 #2
0011111011