1 #include <iostream>       2 #include <stdio.h>       3 #include <cmath>       4 #include <algorithm>       5 #include <iomanip>       6 #include <cstdlib>       7 #include <string>       8 #include <memory.h>       9 #include <vector>      10 #include <queue>      11 #include <stack>      12 #include <map>    13 #include <set>    14 #include <ctype.h>      15 #include <sstream>  16 #define INF 1000000000  17 #define ll long long  18 #define min3(a,b,c) min(a,min(b,c))  19 #define max3(a,b,c) max(a,max(b,c))  20 #define MAXN 100010  21     22 using namespace std;    23  24 bool mk[100010]; 25 bool vis[100010]; 26 bool open[100010]; 27  28 vector<int> E[100010]; 29 queue<int> K; 30  31 int main(){ 32     int t; 33     cin>>t; 34     while(t--){ 35         memset(mk,0,sizeof(mk)); 36         memset(E,0,sizeof(E)); 37         memset(vis,0,sizeof(vis)); 38         memset(open,0,sizeof(open)); 39         while(!K.empty()) K.pop(); 40          41         int n,m,k; 42         cin>>n>>m>>k; 43          44         for(int i=1;i<=k;i++){ 45             int tmp; 46             cin>>tmp; 47         } 48          49         for(int i=1;i<=m;i++){ 50             int u,v; 51             scanf("%d%d",&u,&v); 52             E[u].push_back(v); 53             E[v].push_back(u); 54         } 55          56          57         int L; 58         cin>>L; 59          60         for(int i=1;i<=L;i++){ 61             int tmp; 62             cin>>tmp; 63             mk[tmp]=1; 64             K.push(tmp); 65         } 66         if(L<k){ 67             cout<<"No"<<endl; 68             continue; 69         } 70           71         bool ok=0; 72          73          int nt; 74         int start=K.front(); K.pop(); mk[start]=0; vis[start]=1; 75         queue<int> que; 76         que.push(start); 77         if(!K.empty())  nt=K.front(); 78         while(!que.empty()){ 79             int cur=que.front(); que.pop(); 80             int siz=E[cur].size(); 81             for(int i=0;i<siz;i++){ 82                 int v=E[cur][i]; 83                 if(!vis[v]&&!mk[v]){ 84                     vis[v]=1; 85                     que.push(v); 86                 } 87                  88                 if(v==nt&&!vis[v]){ 89                     vis[v]=1; 90                     que.push(v); 91                     mk[v]=0; 92                     K.pop(); 93                     if(!K.empty()) nt=K.front(); 94                 } 95                 else if(!vis[v]&&mk[v]) 96                     open[v]=1; 97             } 98  99             if(que.empty()){100                 if(open[nt]==1&&!vis[nt]){101                     K.pop();102                     que.push(nt);103                     mk[nt]=0;104                     vis[nt]=1;105                     if(!K.empty())106                         nt=K.front();107                 }108             }109         }110             111         bool flag=true;112         for(int i=1; i<=n; ++i)113            if(!vis[i]){114                    flag=false;115                    break;116            }117         if(K.empty() && flag) ok=1;118         if(ok){119             cout<<"Yes"<<endl;120         }else{121             cout<<"No"<<endl;122         }123         124     }125     return 0;126     127 }

  1 /*  2     题意： 给定一个n个节点m条边的无向图，接着又给出一个序列（由图中的一些节点所组成）   3     问能否按照给定序列的顺序来访问图，并且保证图可以访问完毕！  4       5     思路：是可以走回头路的搜索！那么我们就按照给定的序列进行搜索，如果当前的节点在给定序列中  6     出现过，但是访问的顺序和给定序列的顺序不一样，那么就将该节点标记一下open[]；  7     第一次搜索完毕之后，接着从open[]标记的节点（并且该节点符合给定序列的顺序）开始搜索！   8     最后不要忘记检查图的连通性....   9     如果不清楚，还是看代码吧....  10 */ 11 #include<iostream> 12 #include<cstring> 13 #include<cstdio> 14 #include<algorithm> 15 #include<vector> 16 #define N 100005 17 using namespace std; 18  19 vector<int>g[N]; 20 int vis[N], open[N]; 21 int mk[N], que[N]; 22 int n, m, k, l, cnt; 23 bool flag; 24  25 void init(){ 26     memset(vis, 0, sizeof(vis)); 27     memset(open, 0, sizeof(open)); 28     memset(mk, 0, sizeof(mk)); 29     memset(g, 0, sizeof(g)); 30 } 31  32 void dfs(int u){ 33     vis[u]=1; 34     open[u]=0; 35     if(u==que[cnt]){ 36         ++cnt; 37         if(cnt>k) flag=true; 38     } 39     else if(mk[u]) 40        vis[u]=0; 41     int len=g[u].size(); 42     for(int i=0; i<len; ++i){ 43         int v=g[u][i]; 44         if(!vis[v]){ 45             if(mk[v] && v!=que[cnt]){ 46                 open[v]=1; 47                 continue; 48             } 49             if(open[v] && v!=que[cnt]) 50                 continue; 51             dfs(v); 52         } 53     } 54 } 55  56 int main(){ 57     int t; 58     scanf("%d", &t); 59     while(t--){ 60         init(); 61         scanf("%d%d%d", &n, &m, &k); 62         for(int i=1; i<=k; ++i){ 63             int x; 64             scanf("%d", &x); 65             mk[x]=1; 66         } 67          68         while(m--){ 69             int u, v; 70             scanf("%d%d", &u, &v); 71             g[u].push_back(v); 72             g[v].push_back(u); 73         } 74         scanf("%d", &l); 75         for(int i=1; i<=l; ++i) 76             scanf("%d", &que[i]); 77         if(l<k){ 78             printf("No\n"); 79             continue; 80         } 81         cnt=1; 82         flag=false; 83         open[que[cnt]]=1; 84         while(cnt<=k){//就是从给定序列节点开始并且open标记开始搜索  85                 if(!open[que[cnt]]) break;//如果访问到给定序列的当前节点没有被open标记，说明  86                 dfs(que[cnt]);            //不能按照给定的序列的顺序访问图中的节点  87         } 88         if(flag){ 89                int i; 90                for(i=1; i<=n; ++i) 91                   if(!vis[i])  break; 92                if(i>n) 93                   printf("Yes\n"); 94                   else printf("No\n"); 95         } 96         else 97                   printf("No\n"); 98     } 99     return 0;100 }