2014牡丹江网络zoj3816Generalized Palindromic Number(dfs或者bfs)

时间:2023-03-09 17:45:57
2014牡丹江网络zoj3816Generalized Palindromic Number(dfs或者bfs)
 #include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctype.h>
#include <sstream>
#define INF 1000000000
#define ll long long
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define MAXN 100010 using namespace std; bool mk[];
bool vis[];
bool open[]; vector<int> E[];
queue<int> K; int main(){
int t;
cin>>t;
while(t--){
memset(mk,,sizeof(mk));
memset(E,,sizeof(E));
memset(vis,,sizeof(vis));
memset(open,,sizeof(open));
while(!K.empty()) K.pop(); int n,m,k;
cin>>n>>m>>k; for(int i=;i<=k;i++){
int tmp;
cin>>tmp;
} for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
E[u].push_back(v);
E[v].push_back(u);
} int L;
cin>>L; for(int i=;i<=L;i++){
int tmp;
cin>>tmp;
mk[tmp]=;
K.push(tmp);
}
if(L<k){
cout<<"No"<<endl;
continue;
} bool ok=; int nt;
int start=K.front(); K.pop(); mk[start]=; vis[start]=;
queue<int> que;
que.push(start);
if(!K.empty()) nt=K.front();
while(!que.empty()){
int cur=que.front(); que.pop();
int siz=E[cur].size();
for(int i=;i<siz;i++){
int v=E[cur][i];
if(!vis[v]&&!mk[v]){
vis[v]=;
que.push(v);
} if(v==nt&&!vis[v]){
vis[v]=;
que.push(v);
mk[v]=;
K.pop();
if(!K.empty()) nt=K.front();
}
else if(!vis[v]&&mk[v])
open[v]=;
} if(que.empty()){
if(open[nt]==&&!vis[nt]){
K.pop();
que.push(nt);
mk[nt]=;
vis[nt]=;
if(!K.empty())
nt=K.front();
}
}
} bool flag=true;
for(int i=; i<=n; ++i)
if(!vis[i]){
flag=false;
break;
}
if(K.empty() && flag) ok=;
if(ok){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
} }
return ; }
 /*
题意: 给定一个n个节点m条边的无向图,接着又给出一个序列(由图中的一些节点所组成)
问能否按照给定序列的顺序来访问图,并且保证图可以访问完毕! 思路:是可以走回头路的搜索!那么我们就按照给定的序列进行搜索,如果当前的节点在给定序列中
出现过,但是访问的顺序和给定序列的顺序不一样,那么就将该节点标记一下open[];
第一次搜索完毕之后,接着从open[]标记的节点(并且该节点符合给定序列的顺序)开始搜索!
最后不要忘记检查图的连通性....
如果不清楚,还是看代码吧....
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 100005
using namespace std; vector<int>g[N];
int vis[N], open[N];
int mk[N], que[N];
int n, m, k, l, cnt;
bool flag; void init(){
memset(vis, , sizeof(vis));
memset(open, , sizeof(open));
memset(mk, , sizeof(mk));
memset(g, , sizeof(g));
} void dfs(int u){
vis[u]=;
open[u]=;
if(u==que[cnt]){
++cnt;
if(cnt>k) flag=true;
}
else if(mk[u])
vis[u]=;
int len=g[u].size();
for(int i=; i<len; ++i){
int v=g[u][i];
if(!vis[v]){
if(mk[v] && v!=que[cnt]){
open[v]=;
continue;
}
if(open[v] && v!=que[cnt])
continue;
dfs(v);
}
}
} int main(){
int t;
scanf("%d", &t);
while(t--){
init();
scanf("%d%d%d", &n, &m, &k);
for(int i=; i<=k; ++i){
int x;
scanf("%d", &x);
mk[x]=;
} while(m--){
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
scanf("%d", &l);
for(int i=; i<=l; ++i)
scanf("%d", &que[i]);
if(l<k){
printf("No\n");
continue;
}
cnt=;
flag=false;
open[que[cnt]]=;
while(cnt<=k){//就是从给定序列节点开始并且open标记开始搜索
if(!open[que[cnt]]) break;//如果访问到给定序列的当前节点没有被open标记,说明
dfs(que[cnt]); //不能按照给定的序列的顺序访问图中的节点
}
if(flag){
int i;
for(i=; i<=n; ++i)
if(!vis[i]) break;
if(i>n)
printf("Yes\n");
else printf("No\n");
}
else
printf("No\n");
}
return ;
}