Graph Problem With Small n
wrzSama
·
·
个人记录
题目描述
给你一个 n 个节点、无重边和自环的无向图，对于每对节点 i,j，判断是否存在一条从 i 开始到 j 结束的哈密顿路径。哈密顿路径是由 n-1 条边组成，并经过所有的 n 个节点各一次的路径。
输入格式
第 1 行 1 个正整数 n，表示无向图节点个数。
第 2\sim n+1 行每行 1 个长度为 n 的二进制串 s_i，s_{i,j} 为 1 表示有边连接节点 i 和节点 j，s_{i,j} 为 0 则表示没有。
输出格式
共 n 行每行 1 个长度为 n 的二进制串 t_i，若图中存在从节点 i 到节点 j 的哈密顿路径则 t_{i,j} 为 1，若不存在则 t_{i,j} 为 0。