#MX175. 桥
桥
时间限制:1000ms
空间限制:512MB
题目描述
一条边被称为桥,当且仅当删去该边后,图中的联通块个数增加。
给定 个节点的图,图中可以有重边,和长度为 的序列 ,对于 ,都有 。
图中共有 条边,其中前 条边中,第 条边连接节点 和 。
你需要构造并给出长度为 的 操作序列 ,根据你给出的长度为 的操作序列,在原图的基础上加入以下边从而构造无向图:
对于 ,若
0,则连接无向边 ,否则连接无向边 。
请最小化图中桥的个数,给出你的构造方案。
输入格式
输入第一行,包含 个正整数 。
第二行给定长度为 的正整数序列 。
第三行给定长度为 的正整数序列 。
输出格式
输出一个长度为 的 序列,表示答案。
样例 1 输入
2 2
1 1
2 2
样例 1 输出
01
样例解释 1
图中存在边 ,不存在桥。
样例 2 输入
4 8
1 2 3 1 1 2 3 4
2 3 4 4 2 3 1 2
样例 2 输出
01000000
样例解释 2
依次连接 $(1,5)(2,6)(3,7)(4,8)(1,6)(6,3)(3,8)(1,8)(1,6)(2,7)(3,5)(4,6)$,图中不存在桥。
样例 3 输入
5 4
1 2 4 3
2 3 1 5
样例 3 输出
0101
样例解释 3
图中有 座桥,可以证明不存在桥更少的构造方式。
样例 4 输入
6 6
1 2 3 4 1 1
2 3 4 5 5 6
样例 4 输出
000011
样例解释 4
图中的桥有 ,共 座桥。
样例 5 输入
10 10
2 2 4 5 5 6 7 8 9 10
1 3 3 4 6 1 1 1 1 1
样例 5 输出
1011000000
样例 6 输入
10 12
2 2 4 5 5 6 7 8 9 10 8 7
1 3 3 4 6 1 1 1 1 1 10 9
样例 6 输出
101100110000
样例 7~10
见下发文件。
其中样例 满足特殊性质 。
其中样例 满足特殊性质 。
评测数据规模
| 测试点编号 | 特殊性质 | ||
|---|---|---|---|
| 无 | |||
| 无 | |||
特殊性质 A : 构造一个 个点 条边的图,其中第 条无向边连接 ,保证该图为无重边,无自环的联通图。
特殊性质 B : 。
特殊性质 C : 。