CF1707C.DFS 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:

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.

给你一个由 $n$ 个顶点和 $m$ 条边组成的连通无向图。第 $i$ 条边的权重为 $i$。

以下是求图的最小生成树（MST）的一个错误算法：

vis := 长度为 $n$ 的数组
s := 边的集合

function dfs(u):
vis[u] := true
按照边权从小到大的顺序，遍历与 $u$ 相连的每条边 $(u, v)$
if vis[v] = false
将边 $(u, v)$ 加入集合 $s$
dfs(v)

function findMST(u):
将数组 $vis$ 的所有元素重置为 false
将边集 $s$ 重置为空集
dfs(u)
return 边集 $s$

对每个 $u = 1, 2, \dots, n$，调用 findMST($u$) 均会得到该图的一棵生成树。请判断这些生成树中哪些是最小生成树。

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.

输入的第一行包含两个整数 $n$ 和 $m$（$2\le n\le 10^5$，$n-1\le m\le 2\cdot 10^5$），分别表示图中顶点的数量和边的数量。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1\le u_i, v_i\le n$，$u_i\ne v_i$），描述图中的一条无向边 $(u_i,v_i)$。输入中第 $i$ 条边的权重为 $i$。

保证该图是连通的，且任意两个顶点之间至多存在一条边。

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

你需要输出一个二进制字符串 $s$，其中若 findMST(i) 生成一棵最小生成树（MST），则 $s_i=1$；否则 $s_i = 0$。

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 \gt 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.

以下是第一个示例中给出的图。

该图中仅存在一棵最小生成树（MST）。这棵最小生成树包含边 $(1,2),\,(3,5),\,(1,3),\,(2,4)$，其总权重为 $1+2+3+5=11$。

以下是调用 findMST(1) 过程的部分步骤：

• 重置数组 vis 和边集 s；
• 调用 dfs(1)；
• vis[1] := true；
• 遍历与顶点 1 相连的每条边：$(1,2),\,(1,3)$；
• 将边 $(1,2)$ 加入边集 s，并调用 dfs(2)：
  • vis[2] := true；
  • 遍历与顶点 2 相连的每条边：$(2,1),\,(2,3),\,(2,4)$；
  • 因为 vis[1] = true，故忽略边 $(2,1)$；
  • 将边 $(2,3)$ 加入边集 s，并调用 dfs(3)：
    • ...

最终，算法选出的边为 $(1,2),\,(2,3),\,(3,5),\,(2,4)$，总权重为 $1+4+2+5=12 > 11$，因此 findMST(1) 并未找到最小生成树。

可以证明其余以顶点 2、3、4、5 为起点的 findMST(i) 均能正确找到最小生成树，故答案为 01111。