问题

在接下来的内容中假设我们已经给定了两个图形。第一个图$G=(V, E)$由一组顶点$V$和边$E$组成。第二个图$G_{emb} = (V_{emb}, E_{emb})$也由一组顶点$V_{emb}$和边$E_{emb}$组成，并且应该是一个正方形国王图，其中的顶点从左到右、从上到下进行标记，如下图所示。任务是找到一个映射$s$，将每个顶点$i\in V$分配给一个顶点子集$s(i) ⊂ V_{emb}$，使得：

• 对于任意的顶点$i\in V$，在$G_{emb}$中由$s(i)$诱导的子图是连通的；
• 子集$s(i), s(j) ⊂ V_{emb}$是互不相交的，即对于任意的$i,j \in V$，其中$i\neq j$，我们有$s(i)∩ s(j)=Ø$；
• 对于任意的顶点$i\in V$，子集$s(i)$不能为空。

分数

根据结果映射$s$在单个输入图上运行算法的得分如下评估：

• 给定一个初始分数为$5000$。
• 对于每个边$(i,j) \in E$，如果对应的顶点集$s(i), s(j) ⊂ V_{emb}$由国王图$G_{emb}$的至少一条边连接，我们将初始分数增加$100$分。
• 如果算法找到一个映射$s$，使得对于每一条边$(i,j) \in E$，对应的顶点集$s(i), s(j) ⊂ V_{emb}$由国王图$G_{emb}$的至少一条边连接，则增加$100000$分作为奖励。注意，并非在每个输入图上都能找到满足奖励分数条件的映射$s$。
• 大型集群会减去 $∑ _{u \\in V} (|s(u)|-1)$ 分数。
• 在以下任何情况下，得分将变为 $0$：

1. 如果在$G_{emb}$中任意一个顶点集$s(i)$诱导的子图不连通。参见下图中的示例1。
2. 如果顶点集$s(i), s(j)$相互重叠，即如果任意一个