给你一个无向连通图,由 $$$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。