题意：
给一个n个点m条边的无向图，给k个点。问你是否存在一条路径按顺序访问这些点并且这个图是连通的，就输出Yes，否则输出No
就是说。k=5 然后顺序是 1 2 3 4 5
1->2有路，并且路上不经过3 4 5
2->3有路，并且路上不经过4 5
3->4有路，并且不经过5
4->5有路
思路：
其实就是判断相邻两个点是否连通，用并查集做，先把不相关的点都并起来，然后依次把1相关的边合并，注意在合并1相关边的时候不能合并到2 3 4 5，同理合并2相关的边的时候，不能合并3 4 5，合并完后判断a[i]和a[i-1]这两个点是否同一集合，是的话再判断整个图的是否连通，是的话就输出Yes
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef long long LL;
const int MAXN=1e+5 + 10;
const int MAXM=1e+5 *2 + 10;
const int INF = INT_MAX;
vector <int> e[MAXM];
int path[MAXN];
int Find(int x){
return x==path[x]?x:path[x]=Find(path[x]);
}
int Union(int x,int y){
x=Find(x),y=Find(y);
if(x==y)return false;
path[x]=y;
return true;
}
int hash[MAXN],a[MAXN],b[MAXN];
int main()
{
int n,m,k,t;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<=n;i++){
e[i].clear();
path[i]=i;
hash[i]=0;
}
for(int i=1;i<=k;i++){
scanf("%d",&b[i]);
hash[b[i]]=1;
}
for(int i=0,x,y;i<m;i++){
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
int l,flag=0;
scanf("%d",&l);
for(int i=1;i<=l;i++){
scanf("%d",&a[i]);
if(!hash[a[i]]){
flag=1;
}
}
if(l!=k||flag){
puts("No");
continue;
}
hash[a[1]]=0;
for(int i=1;i<=n;i++){
if(hash[i])continue;
for(int j=0;j<(int)e[i].size();j++){
int v=e[i][j];
if(hash[v])continue;
Union(i,v);
}
}
flag=0;
for(int i=2;i<=k;i++){
hash[a[i]]=0;
for(int j=0;j<(int)e[a[i]].size();j++){
int v=e[a[i]][j];
if(hash[v])continue;
Union(a[i],v);
}
if(Find(a[i])!=Find(a[i-1])){
flag=1;
break;
}
}
if(flag) puts("No");
else {
memset(hash,0,sizeof(hash));
for(int i=1;i<=n;i++){
hash[Find(i)]++;
}
flag=0;
for(int i=1;i<=n;i++){
if(hash[i]==n)flag=1;
}
if(!flag) puts("No");
else puts("Yes");
}
}
return 0;
}
|
