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[100010];
bool vis[100010];
bool open[100010];

vector<int> E[100010];
queue<int> K;

int main(){
    int t;
    cin>>t;
    while(t--){
        memset(mk,0,sizeof(mk));
        memset(E,0,sizeof(E));
        memset(vis,0,sizeof(vis));
        memset(open,0,sizeof(open));
        while(!K.empty()) K.pop();
        
        int n,m,k;
        cin>>n>>m>>k;
        
        for(int i=1;i<=k;i++){
            int tmp;
            cin>>tmp;
        }
        
        for(int i=1;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=1;i<=L;i++){
            int tmp;
            cin>>tmp;
            mk[tmp]=1;
            K.push(tmp);
        }
        if(L<k){
            cout<<"No"<<endl;
            continue;
        }
         
        bool ok=0;
        
         int nt;
        int start=K.front(); K.pop(); mk[start]=0; vis[start]=1;
        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=0;i<siz;i++){
                int v=E[cur][i];
                if(!vis[v]&&!mk[v]){
                    vis[v]=1;
                    que.push(v);
                }
                
                if(v==nt&&!vis[v]){
                    vis[v]=1;
                    que.push(v);
                    mk[v]=0;
                    K.pop();
                    if(!K.empty()) nt=K.front();
                }
                else if(!vis[v]&&mk[v])
                    open[v]=1;
            }

            if(que.empty()){
                if(open[nt]==1&&!vis[nt]){
                    K.pop();
                    que.push(nt);
                    mk[nt]=0;
                    vis[nt]=1;
                    if(!K.empty())
                        nt=K.front();
                }
            }
        }
            
        bool flag=true;
        for(int i=1; i<=n; ++i)
           if(!vis[i]){
                   flag=false;
                   break;
           }
        if(K.empty() && flag) ok=1;
        if(ok){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
        
    }
    return 0;
    
}


/*
    题意: 给定一个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, 0, sizeof(vis));
    memset(open, 0, sizeof(open));
    memset(mk, 0, sizeof(mk));
    memset(g, 0, sizeof(g));
}

void dfs(int u){
    vis[u]=1;
    open[u]=0;
    if(u==que[cnt]){
        ++cnt;
        if(cnt>k) flag=true;
    }
    else if(mk[u])
       vis[u]=0;
    int len=g[u].size();
    for(int i=0; i<len; ++i){
        int v=g[u][i];
        if(!vis[v]){
            if(mk[v] && v!=que[cnt]){
                open[v]=1;
                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=1; i<=k; ++i){
            int x;
            scanf("%d", &x);
            mk[x]=1;
        }
        
        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=1; i<=l; ++i)
            scanf("%d", &que[i]);
        if(l<k){
            printf("No\n");
            continue;
        }
        cnt=1;
        flag=false;
        open[que[cnt]]=1;
        while(cnt<=k){//就是从给定序列节点开始并且open标记开始搜索 
                if(!open[que[cnt]]) break;//如果访问到给定序列的当前节点没有被open标记,说明 
                dfs(que[cnt]);            //不能按照给定的序列的顺序访问图中的节点 
        }
        if(flag){
               int i;
               for(i=1; i<=n; ++i)
                  if(!vis[i])  break;
               if(i>n)
                  printf("Yes\n");
                  else printf("No\n");
        }
        else
                  printf("No\n");
    }
    return 0;
}

目录
相关文章
|
算法
[leetcode] 2039. 网络空闲的时刻 | BFS
题意: 给定一张n个点不含重边的无向图,点的编号从0开始到n-1,两点之间如果有连边,可以认为耗时为1秒 1->n-1的点都需要向0号点发送消息(从第0秒开始) 在0号收到消息之后,会回复消息; 从第一秒开始,如果1->n-1号服务器经过patiennce[]时间都还没有收到回复的消息,那么就会重新发送请求的消息 问最早的网络中没有消息传输的时间是什么时候
92 0
[leetcode] 2039. 网络空闲的时刻 | BFS
|
机器学习/深度学习
2039. 网络空闲的时刻 : 简单「建图 + BFS」运用题
2039. 网络空闲的时刻 : 简单「建图 + BFS」运用题
LeetCode 2039. 网络空闲的时刻(BFS)
LeetCode 2039. 网络空闲的时刻(BFS)
156 0
LeetCode 2039. 网络空闲的时刻(BFS)
2014牡丹江网络赛ZOJPretty Poem(暴力枚举)
/*   将给定的一个字符串分解成ABABA 或者 ABABCAB的形式! 思路:暴力枚举A, B, C串! */ 1 #include 2 #include 3 #include 4 #include 5 6 using namespace std...
672 0
|
2天前
|
安全 网络安全 数据安全/隐私保护
网络安全与信息安全:关于网络安全漏洞、加密技术、安全意识等方面的知识分享
随着互联网的普及,网络安全问题日益严重。本文将从网络安全漏洞、加密技术和安全意识三个方面,探讨如何保护个人信息和网络安全。我们将通过实例分析,了解网络攻击者如何利用安全漏洞进行攻击,以及如何运用加密技术防止数据泄露。同时,我们还将讨论提高个人和企业的安全意识的重要性。
|
3天前
|
SQL 存储 安全
网络安全与信息安全:关于网络安全漏洞、加密技术、安全意识等方面的知识分享##
网络安全与信息安全是当今数字化世界中的重要议题,涉及网络漏洞、加密技术和安全意识等方面。本文将探讨这些关键问题,旨在提升读者对网络安全的认知和应对能力。通过了解常见的网络安全漏洞类型及其影响,掌握加密技术的基本原理和应用,以及培养良好的安全意识和行为习惯,我们可以有效保护自己的隐私和数据安全。网络安全不仅仅是技术问题,更是每个人都应该关注和参与的重要事项。希望通过这篇文章的分享,读者能够增强自身的网络安全意识,共同构建一个更加安全的网络环境。 ##
|
3天前
|
存储 SQL 安全
网络安全与信息安全的全方位解析
本文深入探讨了网络安全和信息安全领域的关键要素,包括网络漏洞、加密技术及安全意识。通过分析这些核心内容,旨在为读者提供实用的知识,以增强个人和企业的信息安全防护能力。我们将从技术角度和管理措施两个维度出发,全面解读如何识别和应对网络威胁,以及如何构建一个安全的网络环境。
|
4天前
|
监控 安全 网络安全
云计算与网络安全:探索云服务中的信息安全实践
【9月更文挑战第36天】在数字化转型的浪潮中,云计算已成为企业IT架构的核心。然而,随着其应用的广泛性,网络安全问题也日益凸显。本文将深入探讨云计算环境中的网络安全挑战,并提出相应的安全策略和技术解决方案。我们将从云服务的基本原理出发,分析常见的网络威胁,并介绍如何通过加密、访问控制和安全监控等手段来保护云环境。文章旨在为读者提供一套实用的云安全指南,帮助他们在享受云计算带来的便利的同时,确保数据的安全和隐私。
30 16