因为每个sensor只记录第一次到访记录,所以dfs到未访问的sensor就返回。以msg[i]为起点dfs,如果能遍历到msg[i+1],则这一步可行。因为遇到sensor就返回,因此i to i+1中间不会经过别的sensor。
智硬的我纠结的另一个地方就是sensor可以重复访问怎么处理,其实,假如a,b,c都是sensor,且顺序为a b c,开始从a dfs 可以同时遍历到b 和 c,那么如果从b开始遍历,可以通过a到c,所以b在之前visited只后就不必再dfs了。之前TLE就是因为重复访问太多,外加设置了一堆变量,memset也会导致TLE....
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> using namespace std; //因为可以重复走,图联通则可以全部访问 int T; int N; int M; int K; int L; vector<int>mp[100100]; int sen[100100]; int msg[100100]; int mark[100100]; int vis[100100]; int used[100100]; int st[100100]; void input() { memset(sen,0,sizeof(sen)); memset(msg,0,sizeof(msg)); //memset(mark,0,sizeof(mark)); memset(vis,0,sizeof(vis)); // memset(used,0,sizeof(used)); scanf("%d %d %d",&N,&M,&K); for(int i=1;i<=N;i++) mp[i].clear(); int tmp; for(int i=1;i<=K;i++) { scanf("%d",&tmp); //sen[i]=tmp; sen[tmp]=1; } int a,b; for(int i=0;i<M;i++) { scanf("%d %d",&a,&b); mp[a].push_back(b); mp[b].push_back(a); } scanf("%d",&L); for(int i=1;i<=L;i++) { scanf("%d",&tmp); msg[i]=tmp; } } void dfs(int node) { vis[node]=1; for(int i=0;i<mp[node].size();i++) { int v=mp[node][i]; if(vis[v]) { continue; } else if(sen[v]) { vis[v]=1; continue; } else { dfs(v); } } // if(sen[node]==1) // { // mark[node]=1; // return; // } // else // { // for(int i=0;i<mp[node].size();i++) // { // used[node]=1;//可以重复访问 // int v=mp[node][i]; // if(!st[v]) // { // st[v]=1; // dfs(v); // st[v]=0; // } // // } // } } void run() { if(K!=L) { printf("No\n"); return; } //mark[msg[1]]=1; //vis[msg[1]]=1; dfs(msg[1]); for(int i=2;i<=L;i++) { //if(!mark[msg[i]]) if(!vis[msg[i]]) { printf("No\n"); return; } else { //memset(mark,0,sizeof(mark)); // memset(st,0,sizeof(st)); //vis[msg[i]]=1; //sen[msg[i]]=0; dfs(msg[i]); } } for(int i=1;i<=N;i++) { if(vis[i]==0) { printf("No\n"); return; } } printf("Yes\n"); return; } int main() { freopen("input.txt","r",stdin); scanf("%d",&T); for(int i=0;i<T;i++) { input(); run(); } return 0; }