#P18604. Graph Problem With Small n
Graph Problem With Small n
Graph Problem With Small n
给出一个有 个顶点的简单无向图。对每对不同的顶点 ,判断是否存在一条从 出发、在 结束,并且恰好经过所有顶点一次的路径。
这样的路径称为哈密顿路径,具有 条边。图不保证连通。
输入格式
第一行一个整数 ,。
随后 行,每行一个长度为 的二进制串。第 行的第 位为 1 表示顶点 之间有边,否则为 0。矩阵对称,对角线全部为 0。
输出格式
输出 行长度为 的二进制串。第 行第 位在存在上述路径时为 1,否则为 0。所有对角线位置必须输出 0。
样例输入 1
4
0110
1010
1101
0010
样例输出 1
0001
0001
0000
1100
样例输入 2
6
010001
101000
010100
001010
000101
100010
样例输出 2
010001
101000
010100
001010
000101
100010
样例输入 3
4
0111
1011
1101
1110
样例输出 3
0111
1011
1101
1110
样例说明
第一组可行的无序端点对是 、。第二组是六个顶点的环,仅原图中相邻的顶点可以作为哈密顿路径的两端。第三组为完全图,所有不同顶点对都可行。