说明

该代码解决的问题是：给定一个由多个区域及其相邻关系构成的地图，以及多个机器人的初始位置，判断是否可以通过同步移动（每次计时器响起时，每个机器人移动到相邻区域）使得所有机器人最终能够聚集到同一个区域。

算法标签

• 图论
• 广度优先搜索（BFS）
• 奇偶性分析

解题思路

1. 输入处理：读取测试用例的数量 t，然后逐个处理每个测试用例。每个测试用例包含区域数量 n、机器人数量 k、每个区域的邻居关系以及机器人的初始位置。
2. 图的构建：使用邻接表 map 存储每个区域的邻居关系。
3. 奇偶性标记：对于每个机器人的初始位置，使用深度优先搜索（DFS）标记从该位置出发，经过奇数步和偶数步能够到达的区域。
4. 统计可达性：统计所有机器人经过奇数步和偶数步能够到达的区域。如果存在一个区域，所有机器人都能在奇数步或偶数步到达该区域，则输出 "YES"；否则输出 "NO"。

分析

• 图的表示：使用邻接表存储区域及其邻居关系，便于后续的遍历和搜索。
• 奇偶性分析：通过标记每个区域是否能在奇数步或偶数步到达，判断机器人是否能够同步移动到同一区域。这是因为机器人每次移动一步，奇偶步数决定了它们能否在同一时间到达同一位置。
• DFS遍历：从每个机器人的初始位置出发，使用DFS遍历所有可能的路径，标记奇数步和偶数步能够到达的区域。
• 可达性统计：统计所有机器人共同能够到达的区域（奇数步或偶数步），判断是否存在满足条件的区域。

实现步骤

1. 读取输入：读取测试用例的数量 t，然后逐个处理每个测试用例。
2. 初始化图结构：使用邻接表 map 存储每个区域的邻居关系。
3. DFS标记奇偶步可达区域：对于每个机器人的初始位置，使用DFS标记奇数步和偶数步能够到达的区域。
4. 统计共同可达区域：检查是否存在一个区域，所有机器人都能在奇数步或偶数步到达该区域。
5. 输出结果：根据统计结果输出 "YES" 或 "NO"。

代码

#ifdef _MSC_VER
#define DEBUG
#define _CRT_SECURE_NO_DEPRECATE
#endif
 
#include <fstream>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <functional>
#include <ctype.h>
#include <vector>
#define MAX 110
using namespace std;
 
vector<int> map[MAX];
bool odd[MAX],even[MAX];
int odd_count[MAX],even_count[MAX];
 
void init(const int &n)
{
	for(int i=0;i<MAX;++i)
		map[i].clear();
	memset(odd_count,0,sizeof(odd_count));
	memset(even_count,0,sizeof(even_count));
}
 
void dfs(const int &x,const int &step)
{
	bool flag=false;
	if( !odd[x] && step%2)
	{
		flag=true;
		odd[x]=true;
	}
	if( !even[x] && step%2==0)
	{
		flag=true;
		even[x]=true;
	}
	if(flag)
	{
		for(size_t i=0;i<map[x].size();++i)
			dfs(map[x][i],step+1);
	}
}
 
int main(void)
{
#ifdef DEBUG  
	freopen("../stdin.txt","r",stdin);
	freopen("../stdout.txt","w",stdout); 
#endif  
 
	int n,m,ncase=1;
	int id,u,v,tmp;
	scanf("%d",&ncase);
 
	while(ncase--)
	{
		scanf("%d%d",&n,&m);
		init(n);
		for(int i=0;i<n;++i)
		{
			scanf("%d%d",&id,&tmp);
			for(int j=0;j<tmp;++j)
			{
				scanf("%d",&v);
				map[id].push_back(v);
			}
		}
		for(int i=0;i<m;++i)
		{
			memset(odd,false,sizeof(odd));
			memset(even,false,sizeof(even));
			scanf("%d",&u);
			dfs(u,0);
			for(int j=0;j<MAX;++j)
			{
				if(odd[j])
					++odd_count[j];
				if(even[j])
					++even_count[j];
			}
		}
		bool ans=false;
		for(int i=0;i<MAX && !ans;++i)
		{
			if(odd_count[i]==m)
				ans=true;
			if(even_count[i]==m)
				ans=true;
		}
		if(ans)
			printf("YES\n");
		else
			printf("NO\n");
	}
 
	return 0;
}