首页 > 代码库 > ZOJ 3811
ZOJ 3811
亏大了,当时没做,被另一道题目题意给坑了,其实把他建成一个双向图,首先l <k 或者整个图 无法连通 那么肯定是No,在这个双向图里,以 L 个触发器 亮的顺序来,先从第一个开始深搜,遇到一个触发器 就停止往下搜,这样 当前第一个触发器 与其它 几个触发器之间有路径可达,并放在一个集合里,接下来判断 第二个触发器是否在这个集合里,以此类推,到第二个触发器 也去深搜,搜完 再判断第三个触发器 是否在这个集合里推到最后一个即可,而且搜索过的点可以不用再搜索,降低了复杂度,因为若都在一个集合里,肯定是可以到达的,
看题解多数使用了并查集,不过也有几个题解的的思路 差不多也是这个样子,解法挺多的
int t; int n,m,k; int nnum[100000 + 55]; bool vis[100000 + 55]; bool flag[100000 + 55]; vector<int > G[100000 + 55]; set<int > my_set; void init() { my_set.clear(); memset(vis,false,sizeof(vis)); memset(nnum,0,sizeof(nnum)); memset(flag,false,sizeof(flag)); for(int i=0;i<100000 + 55;i++)G[i].clear(); } bool input() { while(scanf("%d %d %d",&n,&m,&k)) { int xx; for(int i=0;i<k;i++) scanf("%d",&xx); int q = m; while(q--) { int u,v; scanf("%d %d",&u,&v); G[u].push_back(v); G[v].push_back(u); } return false; } return true; } void dfs(int u) { vis[u] = true; for(int i=0;i<G[u].size();i++) { int v = G[u][i]; if(!vis[v]) { if(flag[v]){ my_set.insert(v);continue;} dfs(v); } } } void cal() { int l; scanf("%d",&l); for(int i=0;i<l;i++) { scanf("%d",&nnum[i]); flag[nnum[i]] = true; } if(l < k){puts("No");return ;} dfs(nnum[0]); for(int i=1;i<l;i++) { if(my_set.find(nnum[i]) == my_set.end()) { puts("No");return ; } dfs(nnum[i]); } for(int i=1;i<=n;i++) { if(!vis[i]) {puts("No");return ;} } puts("Yes"); } void output() { } int main() { scanf("%d",&t); while(t--) { init(); if(input())return 0; cal(); output(); } return 0; }
ZOJ 3811
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。