题意:
这个是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 440000 using 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;
}