首页 > 代码库 > zoj 3811 Untrusted Patrol DFS SET
zoj 3811 Untrusted Patrol DFS SET
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5343
当时是一个学弟过的,真心没想出来,回想起来其实可能有点后悔做ACM了,确实智商不够......
11去牡丹江比赛,如果悲剧,ACM生涯就彻底悲剧了,尽量出结果......啥不说,专心刷题
此题还是参考了答案,,,
题目要求:按照次序访问某些点,如果能满足而且能遍历全图,输出yes否则no
学到:
1、是不是能按照规定次序,那么就这么看,按照规定次序,DFS第一个点,过程中如果遇到第二个点,加入Set,从第二个点开始搜,如果能遇到第三个点,加入Set,直到所有点都能遍历完。
最后检查图是不是被遍历一遍
2、检查图是不是联通的另一种方法:
DFS的过程中vis数组记录,最后扫一遍,看是不是都遍历过了
3、DFS写法注意,DFS到监控点马上停止,否则的话,就不能保证按照规定次序,哎,DFS功力不够没想到啊
//#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <iostream> #include <iomanip> #include <cmath> #include <map> #include <set> #include <queue> using namespace std; #define ls(rt) rt*2 #define rs(rt) rt*2+1 #define ll long long #define ull unsigned long long #define rep(i,s,e) for(int i=s;i<e;i++) #define repe(i,s,e) for(int i=s;i<=e;i++) #define CL(a,b) memset(a,b,sizeof(a)) #define IN(s) freopen(s,"r",stdin) #define OUT(s) freopen(s,"w",stdout) const ll ll_INF = ((ull)(-1))>>1; const double EPS = 1e-8; const double pi = acos(-1.0); const int INF = 100000000; const int MAXN = 100000+50; vector<int>g[MAXN*2];// set<int>s; int n,m,k,k2; int vis[MAXN],pos[MAXN],sm[MAXN]; void dfs(int u) { vis[u]=1; int si=g[u].size(); for(int i=0;i<si;i++) { int v=g[u][i]; if(!vis[v]) { //vis[v]=1; if(pos[v])s.insert(v); else dfs(v); // } } } void read() { CL(vis,0); CL(pos,0); s.clear(); scanf("%d%d%d",&n,&m,&k); for(int i=0;i<=n;i++)g[i].clear(); int u,v; for(int i=0; i<k; i++) scanf("%d",&u); for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } scanf("%d",&k2); for(int i=0;i<k2;i++) { scanf("%d",&sm[i]); pos[sm[i]]=1; } if(k2<k) { puts("No"); return; } dfs(sm[0]); for(int i=1;i<k2;i++) { if(s.find(sm[i]) == s.end()) { puts("No"); return; } else dfs(sm[i]); } for(int i=1;i<=n;i++) if(!vis[i]) { puts("No"); return; } puts("Yes"); } int main() { //IN("zoj3811.txt"); int ncase; scanf("%d",&ncase); while(ncase--) { read(); } return 0; }
zoj 3811 Untrusted Patrol DFS SET
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。