ZOJ 3811 Untrusted Patrol 並查集
題目鏈接：點擊打開鏈接
題意：
給定n個點m條邊的無向圖，k個觸發器。
下面k個數表示觸發器安裝在哪幾個點。
下面m行給出邊
最後有l個信號，
給出信號發出的觸發器的順序。
每個觸發器只會發出一次信號，且一個點只有一個觸發器。
有一個人在遍歷圖。
每經過一個點，那個點的觸發器就會發出信號，問是否存在一種走法使得這個人遍歷了所有點且觸發器發出的信號順序和給出的一樣。
思路：
先把無觸發器的點放到圖裡。
然後根據觸發器的信號順序把點依次加入圖中，加入時只添加（與無觸發器點相連的邊）
然後判斷這個點能否與之前的圖連通。bfs+並查集判斷。
==其實並查集就夠了，寫的時候有腦洞，bfs就冒出來了
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll int
typedef pair pii;
#define M 400010
#define N 200010
int f[N];
int find(int x){return x==f[x]?x:f[x] = find(f[x]);}
void Union(int x,int y){
int fx = find(x), fy = find(y);
if(fx==fy)return ;
if(fx>fy)swap(fx,fy);
f[fx] = fy;
}
struct Edge{
int from, to, nex;
}edge[M<<1];
int head[N], edgenum;
void init(){memset(head, -1, sizeof head); edgenum = 0;}
void add(int u, int v){
Edge E = {u, v, head[u]};
edge[edgenum] = E;
head[u] = edgenum++;
}
int n, m, k, l;
int is[N], vis[N];
vectorG, E[N];
void ADD(int x){
for(int i = 0; i < E[x].size(); i++){
if(is[E[x][i]] == 0)
add(x, E[x][i]);
}
is[x] = 0;
}
void bfs(int x){
queueq; q.push(x);
vis[x] = 1;
while(!q.empty()){
int u = q.front(); q.pop();
for(int i = head[u]; ~i; i = edge[i].nex)
{
int v = edge[i].to;
Union(v, x);
if(vis[v])continue;
vis[v] = 1;
q.push(v);
}
}
}
bool solve(){
scanf("%d %d %d",&n,&m, &k);
init();
int i, j, u, v;
for(i = 1; i <= n; i++) {
vis[i] = is[i] = 0;
E[i].clear();
}
for(i = 1; i <= k; i++) { scanf("%d",&j); is[j] = 1; }
while(m--){
scanf("%d %d", &u, &v);
E[u].push_back(v); E[v].push_back(u);
}
G.clear();
scanf("%d", &l);
for(i = 1; i <= l; i++) { scanf("%d", &j); G.push_back(j); }
//若觸發器沒有全響，就不行
if(k!=l)return false;
//若沒有觸發器一定可以。
if(k == 0) return true;
for(i = 1; i <= n; i++)
{
if(is[i] == 0)
{
for(j = 0; j < E[i].size(); j++)
if(is[E[i][j]]==0)
add(i, E[i][j]);
}
}
for(i = 1; i <= n; i++) f[i] = i;
for(i = 0; i < G.size(); i++) {
u = G[i];
ADD(u);
bfs(u);
if(i-1>=0){
find(G[i]); find(G[i-1]);
if(f[G[i]] != f[G[i-1]])
return false;
}
}
for(i = 1; i <= n; i++) if(vis[i] == 0) return false;
return true;
}
int main(){
int T; scanf("%d",&T);
while(T--)
solve() ? puts("Yes"):puts("No");
return 0;
}
/*
99
5 5 3
1 2 4
1 2
2 3
3 1
1 4
4 5
3
4 2 1
5 5 3
1 2 4
1 2
2 3
3 1
1 4
4 5
3
4 1 2
7 8 3
1 3 5
1 2
1 3
2 3
2 4
3 6
5 4
5 7
6 7
3
5 3 1
7 8 5
3 6 4 5 7
1 2
1 3
2 3
2 4
3 6
5 4
5 7
6 7
5
3 6 4 5 7
7 8 5
3 6 4 5 7
1 2
1 3
2 3
2 4
3 6
5 4
5 7
6 7
5
3 6 5 4 7
8 8 5
3 6 4 5 7
1 2
1 3
2 3
2 4
3 6
5 4
5 7
6 7
5
3 6 4 5 7
ans:
N
Y
Y
Y
N
N
*/
