← 返回题目列表

Codeforces · 1707/C

C. DFS 树

中文机器翻译题面 查看原题

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

这是查找图的最小生成树(MST)的错误算法:

每个调用 findMST(1)、findMST(2)、...、findMST(n) 都会为您提供图的生成树。确定这些树中哪一棵是最小生成树。

输入

输入的第一行包含两个整数 $$$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$$$。

保证图是连通的,并且任意一对顶点之间至多有一条边。

输出

您需要输出一个二进制字符串$$$s$$$,其中如果findMST(i)创建MST,则$$$s_i=1$$$,否则$$$s_i = 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,2),(3,5),(1,3),(2,4)$$$,其权重为$$$1+2+3+5=11$$$。

下面是调用 findMST(1) 的部分过程:

- 重置数组vis和边集s;
- 调用 dfs(1);
- vis[1] := true;
- 迭代每条边 $$$(1,2),(1,3)$$$;
- 将边 $$$(1,2)$$$ 添加到边集 s 中,调用 dfs(2): vis[2] := true 迭代每条边 $$$(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)并没有找到最小生成树。

可以证明,其他树都是MST,所以答案是01111。