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说明
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.Input
题意翻译
## 题目描述 有一图有$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)$时，会返回这个图的最小生成树，你要判定那些是正确的最小生成树Output
题目大意：给定一个包含n个顶点和m条边的连通无向图，每条边的权重为i。有一个寻找最小生成树（MST）的错误算法，需要判断对于每个起点i，调用findMST(i)得到的是否为最小生成树。
输入数据格式：第一行包含两个整数n和m，表示顶点数和边数。接下来m行，每行包含两个整数ui和vi，描述图中的一条无向边(ui,vi)。保证图是连通的，且任意两个顶点间最多只有一条边。
输出数据格式：输出一个长度为n的01字符串s，如果findMST(i)得到的是MST，则si=1，否则si=0。
输入输出样例：
输入样例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
```
说明：对于输入样例1，只有一棵MST，权重为1+2+3+5=11。调用findMST(1)时，最终选择的边为(1,2),(2,3),(3,5),(2,4)，总权重为1+4+2+5=12>11，所以findMST(1)没有找到MST。其他树都是MST，所以答案为01111。题目大意：给定一个包含n个顶点和m条边的连通无向图，每条边的权重为i。有一个寻找最小生成树（MST）的错误算法，需要判断对于每个起点i，调用findMST(i)得到的是否为最小生成树。 输入数据格式：第一行包含两个整数n和m，表示顶点数和边数。接下来m行，每行包含两个整数ui和vi，描述图中的一条无向边(ui,vi)。保证图是连通的，且任意两个顶点间最多只有一条边。 输出数据格式：输出一个长度为n的01字符串s，如果findMST(i)得到的是MST，则si=1，否则si=0。 输入输出样例： 输入样例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 ``` 说明：对于输入样例1，只有一棵MST，权重为1+2+3+5=11。调用findMST(1)时，最终选择的边为(1,2),(2,3),(3,5),(2,4)，总权重为1+4+2+5=12>11，所以findMST(1)没有找到MST。其他树都是MST，所以答案为01111。
输入数据格式：第一行包含两个整数n和m，表示顶点数和边数。接下来m行，每行包含两个整数ui和vi，描述图中的一条无向边(ui,vi)。保证图是连通的，且任意两个顶点间最多只有一条边。
输出数据格式：输出一个长度为n的01字符串s，如果findMST(i)得到的是MST，则si=1，否则si=0。
输入输出样例：
输入样例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
```
说明：对于输入样例1，只有一棵MST，权重为1+2+3+5=11。调用findMST(1)时，最终选择的边为(1,2),(2,3),(3,5),(2,4)，总权重为1+4+2+5=12>11，所以findMST(1)没有找到MST。其他树都是MST，所以答案为01111。题目大意：给定一个包含n个顶点和m条边的连通无向图，每条边的权重为i。有一个寻找最小生成树（MST）的错误算法，需要判断对于每个起点i，调用findMST(i)得到的是否为最小生成树。 输入数据格式：第一行包含两个整数n和m，表示顶点数和边数。接下来m行，每行包含两个整数ui和vi，描述图中的一条无向边(ui,vi)。保证图是连通的，且任意两个顶点间最多只有一条边。 输出数据格式：输出一个长度为n的01字符串s，如果findMST(i)得到的是MST，则si=1，否则si=0。 输入输出样例： 输入样例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 ``` 说明：对于输入样例1，只有一棵MST，权重为1+2+3+5=11。调用findMST(1)时，最终选择的边为(1,2),(2,3),(3,5),(2,4)，总权重为1+4+2+5=12>11，所以findMST(1)没有找到MST。其他树都是MST，所以答案为01111。