2014牡丹江网络zoj3816Generalized Palindromic Number（dfs或者bfs）-白红宇

1 #include 
      
              2 #include 
       
               3 #include 
        
                4 #include 
         
                 5 #include 
          
                  6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                  13 #include 
                  
                    14 #include 
                   
                     15 #include 
                    
                      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
                     
                       E[100010]; 29 queue
                      
                        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

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

1 /*  2     题意： 给定一个n个节点m条边的无向图，接着又给出一个序列（由图中的一些节点所组成）   3     问能否按照给定序列的顺序来访问图，并且保证图可以访问完毕！  4       5     思路：是可以走回头路的搜索！那么我们就按照给定的序列进行搜索，如果当前的节点在给定序列中  6     出现过，但是访问的顺序和给定序列的顺序不一样，那么就将该节点标记一下open[]；  7     第一次搜索完毕之后，接着从open[]标记的节点（并且该节点符合给定序列的顺序）开始搜索！   8     最后不要忘记检查图的连通性....   9     如果不清楚，还是看代码吧....  10 */ 11 #include
      
        12 #include
       
         13 #include
        
          14 #include
         
           15 #include
          
            16 #define N 100005 17 using namespace std; 18  19 vector
           
            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
            
             n) 93 printf("Yes\n"); 94 else printf("No\n"); 95 } 96 else 97 printf("No\n"); 98 } 99 return 0;100 }