ZOJ Problem Set - 3811 Untrusted Patrol

Edward is a rich man. He owns a large factory for health drink production. As a matter of course, there is a large warehouse in the factory.

To ensure the safety of drinks, Edward hired a security man to patrol the warehouse. The warehouse has N piles of drinks and M passageways connected them (warehouse is not big enough). When the evening comes, the security man will start to patrol the warehouse following a path to check all piles of drinks.

Unfortunately, Edward is a suspicious man, so he sets sensors on K piles of the drinks. When the security man comes to check the drinks, the sensor will record a message. Because of the memory limit, the sensors can only record for the first time of the security man‘s visit.

After a peaceful evening, Edward gathered all messages ordered by recording time. He wants to know whether is possible that the security man has checked all piles of drinks. Can you help him?

The security man may start to patrol at any piles of drinks. It is guaranteed that the sensors work properly. However, Edward thinks the security man may not works as expected. For example, he may digs through walls, climb over piles, use some black magic to teleport to anywhere and so on.

Input

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:

The first line contains three integers N (1 <= N <= 100000), M (1 <= M <= 200000) and K (1 <= K <= N).

The next line contains K distinct integers indicating the indexes of piles (1-based) that have sensors installed. The following M lines, each line contains two integers A_i and B_i (1 <= A_i, B_i<= N) which indicates a bidirectional passageway connects piles A_i and B_i.

Then, there is an integer L (1 <= L <= K) indicating the number of messages gathered from all sensors. The next line contains L distinct integers. These are the indexes of piles where the messages came from (each is among the K integers above), ordered by recording time.

Output

For each test case, output "Yes" if the security man worked normally and has checked all piles of drinks, or "No" if not.

Sample Input

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

Sample Output

No
Yes

Source:  The 2014 ACM-ICPC Asia Mudanjiang Regional First Round

在一个生产保健饮料的工厂仓库中有N个地点放了饮料，N个地点之间有M个通道。老板雇了保安夜晚来巡逻每一个存放饮料的地点。但是老板比较多疑，他在K个地点中装了传感器，由于内存限制，传感器只能显示人第一次到达该地点的时间。如果情况不安全的话，那么说明可能有另外的人进来了导致传感器记录的顺序不正常，就像是有人会穿墙或者传送之类的魔法一样。现在，需要你根据传感器的记录情况来判断情况是否安全，如果情况安全且保安能够顺利巡逻到存放饮料的每个点的话输出“Yes”，否则的话输出“No”。

根据给出的L个起点依次枚举，每次bfs，碰到传感器标记路过但不压入队列，每次bfs之前如果发现起点之前没有路过，那么就是No

这样每个点最多搜索一次，节省了时间

#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
#include<stack>
#include<set>
using namespace std;
struct Edge
{
	int to,next;
}edge[400010];
bool ban[100010],vis[100010];
int tail,head[100010],goal[100010];
void add(int s,int e)
{
	edge[tail].to=e;
	edge[tail].next=head[s];
	head[s]=tail++;	
}
void bfs(int s)
{
	queue<int>qq;
	qq.push(s);
	while(qq.size())
	{
		int from=qq.front();
		qq.pop();
		vis[from]=1;
		if(ban[from])
			continue;
		for(int i=head[from];i!=-1;i=edge[i].next)
		{
			int to=edge[i].to;
			if(!vis[to])
				qq.push(to);
		}
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,m,k;
		scanf("%d%d%d",&n,&m,&k);
		memset(ban,0,sizeof(ban));
		for(int i=0;i<k;i++)
		{
			int t;
			scanf("%d",&t);
			ban[t]=1;
		}
		tail=0;
		memset(head,-1,sizeof(head));
		while(m--)
		{
			int s,e;
			scanf("%d%d",&s,&e);
			add(s,e);
			add(e,s);
		}
		int L;
		scanf("%d",&L);
		for(int i=0;i<L;i++)
			scanf("%d",goal+i);
		bool flag=0;
		if(k!=L)
			flag=1;
		memset(vis,0,sizeof(vis));
		for(int i=0;i<L&&!flag;i++)
		{
			ban[goal[i]]=0;
			if(i==0)
				vis[goal[i]]=1;
			if(vis[goal[i]])
				bfs(goal[i]);
			else
				flag=1;
		}
		for(int i=1;i<=n&&!flag;i++)
			if(!vis[i])
				flag=1;
		puts(flag?"No":"Yes");
	}
}

原文：http://blog.csdn.net/stl112514/article/details/43816921