The 2014 ACM-ICPC Asia Mudanjiang Regional First Round C

题意：
      这个是The 2014 ACM-ICPC Asia Mudanjiang Regional First Round 的C题，这个题目当时自己想的很复杂，想的是优先队列广搜，然后再在前向星里排序，结果写了好长，然后wa掉了，还好后来被队友A了，题意是给你一个无向图，然后让你遍历所有的点，但是有一些点的之间的遍历顺序有限制，最后问你能否遍历所有点。

思路：

       今早起来才用自己的思路A了这个题，其实我们可以按照限制的顺序，一个一个枚举，对于当前的这个点，我们从它开始搜，见到限制的点就continue，其他的就继续遍历，只要当前的这个点能找到一个之前限制点搜的时候遍历过的点就行（除了第一个点），就这样遍历到最后，然后看看是否所有的点都被mark了就行了，具体看代码吧。

#include<stdio.h> #include<string.h> #include<queue>#define N_node 110000 #define N_edge 440000using namespace std;typedef struct {int to ,next; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int mk_cgq[N_node] ,mark[N_node] ,mk[N_node]; int cgq[N_node]; int ok; queue<int>q;void add(int a ,int b) {E[++tot].to = b;E[tot].next = list[a];list[a] = tot; }void DFS(int s) {for(int k = list[s] ;k ;k = E[k].next){int to = E[k].to;if(mark[to]) ok = 1;if(mk[to] || mk_cgq[to]) continue;mk[to] = 1;q.push(to);DFS(to);} }int main () {int n ,m ,l ,t ,a ,b ,i ,k;scanf("%d" ,&t);while(t--){scanf("%d %d %d" ,&n ,&m ,&k);for(i = 1 ;i <= k ;i ++)scanf("%d" ,&a);memset(list ,0 ,sizeof(list)) ,tot = 1;for(i = 1 ;i <= m ;i ++){scanf("%d %d" ,&a ,&b);add(a ,b) ,add(b ,a);}scanf("%d" ,&l);memset(mk_cgq ,0 ,sizeof(mk_cgq));for(i = 1 ;i <= l ;i ++){scanf("%d" ,&cgq[i]);mk_cgq[cgq[i]] = 1;}if(l != k){printf("No\n");continue;}memset(mark ,0 ,sizeof(mark));memset(mk ,0 ,sizeof(mk));for(i = 1 ;i <= k ;i ++){mk[cgq[i]] = 1;ok = 0;while(!q.empty())q.pop();DFS(cgq[i]);while(!q.empty()){mark[q.front()] = 1;q.pop();}mark[cgq[i]] = 1;if(!ok && i != 1) break;}if(i != k + 1){printf("No\n");continue;} for(i = 1 ;i <= n ;i ++)if(!mark[i]) break;if(i != n + 1) printf("No\n");else printf("Yes\n");}return 0; }

总结

以上是生活随笔为你收集整理的The 2014 ACM-ICPC Asia Mudanjiang Regional First Round C的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。