P1612. 测地集问题

ID: 613
远程评测题
时间限制: 1000ms
内存限制: 10MiB
尝试次数: 0
通过次数: 0
难度: （无）
上传者: Hydro
标签:

题目描述

设 ( G = (V, E) ) 为不含自环和重边的连通图，其中 ( V ) 和 ( E ) 分别为图 ( G ) 的顶点集和边集。对于任意两个顶点 ( u, v \in V )，顶点 ( u ) 和 ( v ) 在 ( G ) 中的距离是 ( u-v ) 最短路径上的边数。( u ) 和 ( v ) 之间的最短路径称为 ( u-v ) 测地线。记 ( I(u, v) ) 为满足以下条件的顶点集：当且仅当某顶点在某条 ( u-v ) 测地线上时，该顶点属于 ( I(u, v) )。对于集合 ( S \subseteq V )，定义 ( I(S) = \cup_{u,v \in S} I(u, v) )。图 ( G ) 中的顶点集 ( D ) 称为测地集，当且仅当 ( I(D) = V )。测地集问题要求验证 ( D ) 是否为测地集。

以图 3 为例：在图 3 中，( I(2, 5) = {2, 3, 4, 5} )，因为顶点 2 和 5 之间有两条最短路径，顶点 3 和 4 分别位于其中一条最短路径上。但 ( I(2, 5) ) 不是测地集，因为 ( I(2, 5) \neq V )。直观上，顶点集 ( {1, 2, 3, 4, 5} ) 是 ( G ) 的一个测地集。顶点集 ( D = {1, 2, 5} ) 也是 ( G ) 的测地集，因为顶点 3（对应地，顶点 4）位于顶点 1 和 5（对应地，顶点 2 和 5）的最短路径上，因此 ( I(D) = V )。此外，顶点集 ( {1, 3, 4} ) 和 ( {1, 4, 5} ) 也是测地集。

然而，( D = {3, 4, 5} ) 不是测地集，因为顶点 1 不在 ( I(D) ) 中。

输入格式

输入文件包含一个给定的图和若干测试用例。

• 第一行包含一个整数 ( n )，表示图的顶点数（( 2 \leq n \leq 40 )），顶点按 ( 1 ) 到 ( n ) 编号，每个顶点标号唯一。
• 接下来 ( n ) 行依次表示顶点 ( i )（( i = 1, 2, \dots, n )）的相邻顶点。例如，样例输入的第二行表示顶点 1 与顶点 2、3 相邻。每行中任意两个整数之间至少用一个空格分隔。
• 这 ( n ) 行之后是一行整数，表示测试用例的数量。
• 每个测试用例占一行，表示一个给定的顶点子集 ( D )，需判断 ( D ) 是否为测地集。
  

输出格式

对于每个测试用例，若 ( D ) 是测地集，输出一行 "yes"，否则输出 "no"。

输入数据示例 1

5  
2 3  
1 3 4  
1 2 5  
2 5  
3 4  
6  
1 2 3 4 5  
1 2 5  
2 4  
1 3 4  
1 4 5  
3 4 5  

输出数据示例 1

yes  
yes  
no  
yes  
yes  
no  

来源

Asia Kaohsiung 2003