首页 > 代码库 > zoj 3811 条件下判定某遍历序列的合法性/ 一遍 dfs
zoj 3811 条件下判定某遍历序列的合法性/ 一遍 dfs
题意:在某些点上安装首次访问时候会报警的机器,给出报警嗲你的顺序,问是否合法。
思路:按所给的序列,每个进来时判断这个点目前能否达到(第一个可达总是),若能,则该点进行扩展遍历所有没有报警器的点,遇到有的报警器的标记可达就返回。
预判:判断原图连图性。
#include<iostream> #include<queue> #include<cstdio> #include<vector> #include<cstring> using namespace std; vector<vector<int> >g(100010); int has[100010]; vector<int>jud; int n,m,k,l; int vis[100010]; bool bfs() { memset(vis,0,sizeof(vis)); queue<int>q; q.push(1); vis[1]=1; while(!q.empty()) { int cur=q.front(); q.pop(); for(int i=0;i<g[cur].size();i++) { int v=g[cur][i]; if(vis[v]==0) { vis[v]=1; q.push(v); } } } for(int i=1;i<=n;i++) { if(vis[i]==0) { return 0; } } return 1; } void dfs(int u) { if(has[u]==1&&vis[u]==0) { vis[u]=1; return ; } for(int i=0;i<g[u].size();i++) { int v=g[u][i]; if(vis[v]==0&&has[v]==0) { vis[v]=1; dfs(v); } else if(vis[v]==0) { dfs(v); } } return ; } void init() { for(int i=0;i<=n;i++) { has[i]=0; g[i].clear(); vis[i]=0; } jud.clear(); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&k); init(); int tx,ty; for(int i=0;i<k;i++) { scanf("%d",&tx); has[tx]=1; } for(int i=0;i<m;i++) { scanf("%d%d",&tx,&ty); g[tx].push_back(ty); g[ty].push_back(tx); } scanf("%d",&l); for(int i=0;i<l;i++) { scanf("%d",&tx); jud.push_back(tx); } if(l!=k||bfs()==0) { printf("No\n");continue; } memset(vis,0,sizeof(vis)); bool marks=1; vis[jud[0]]=1; for(int i=0;i<l;i++) { if(vis[jud[i]]==0) { marks=0;break; } dfs(jud[i]); } if(marks) printf("Yes\n"); else printf("No\n"); } return 0; }
zoj 3811 条件下判定某遍历序列的合法性/ 一遍 dfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。