题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3811
解题报告：一个无向图上有n个点和m条边，其中有k个点上安装了传感器，当有人第一次从安装了传感器的点上经过时，在控制室就会收到一个信号，现在保安制定 了一条路线目的是要将所有的点都巡逻一遍，然后在控制室收到了 L 次信号，按顺序给出收到信号的点，问这条路线是否是有可能的？
路线的不可能的情况比如收到信号的点的顺序是123，但是在无向图上要到达2这个点必定先经过3，那么这种情况就是不可能的，因为要经过2之前必定经过3，所以2之前一定会有个3.这题的思路是这样的，用dfs从第一个点开始搜，当当前点的下一个点是没有传感器的可以直接走，如果有传感器的而且刚好是路线上的下一个点，也是直接走，如果是有传感器但又不是路线上的下一个点，则先把这个点放入到一个集合里面去，当所有能走的点都走完了，再在这个集合里面找路线上的下一个点是不是在这个集合里面，最后当集合空了的时候就可以退出了，而且每次走完点之后都要标记掉。另外两个重要的就是首先要判断L 是不是等于k，因为要走完所有的点，当L小于K时，走K-L 的这些点的时候肯定会发出信号，但这些信号又不是路线上的，所以不符合。另一个是要判断这个无向图是不是个连通图，这个简单，如果不是连通图必定会有走不到的点。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = ;
vector<int> vet[maxn];
int flag[maxn];
int T,n,m,k,l,L[maxn],cizi[maxn],visit[maxn],is[maxn],num;
void find(int p,int* is)
{
if(is[p] == ) return ;
num++;
is[p] = ;
for(int i = ;i < vet[p].size();++i)
find(vet[p][i],is);
} int is_connect(int n) //判断是否是连通图
{
num = ;
memset(is,,sizeof(is));
find(,is);
return num == n;
}
void dfs(int s,int* visit,int& p)
{
if(visit[s]) return ;
visit[s] = ;
if(flag[s]) p++;
for(int i = ;i < vet[s].size();++i)
{
int nx = vet[s][i];
if(flag[nx] && L[p+] != nx) //下一个点是有传感器的，但不是当前位置上的下一个点，则加入集合
cizi[nx] = ;
else dfs(nx,visit,p);
}
} int main()
{ scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
int a,b;
memset(flag,,sizeof(flag)); //flag[i] = 1表示i点有传感器
for(int i = ;i <= k;++i)
{
scanf("%d",&a);
flag[a] = ;
}
for(int i = ;i <= n;++i)
vet[i].clear();
for(int i = ; i<= m;++i)
{
scanf("%d%d",&a,&b);
vet[a].push_back(b);
vet[b].push_back(a);
}
scanf("%d",&l);
for(int i = ;i <= l;++i)
scanf("%d",&L[i]);
if(l != k || (!is_connect(n))) //l < k或者不是连通图
{
// if(!is_connect(n)) puts("不是连通图");
puts("No");
continue;
}
int num_cizi = ;
memset(cizi,,sizeof(cizi)); //把集合清空
memset(visit,,sizeof(visit));
cizi[L[]] = ; //路径上的第一个点加入集合
int s = L[],p = ; //当前走到的路径上的指针
while(p < l && cizi[s])
{
dfs(s,visit,p);
// printf("p = %d\n",p);
if(cizi[L[p+]] == )
s = L[p+];
else break;
}
printf(p == l? "Yes\n":"No\n");
}
return ;
}
/*
44
6 6 6
1 2 3 4 5 6
1 6
6 3
6 2
2 3
2 5
3 4
6
1 6 2 5 3 4
*/