题解 P2189 【小Z的传感器】

· · 题解

思路

看前后两次顺序是否正确，其实就是判断能否通过未打上标记的节点相互到达 。本质上就是判断两个节点是否在同一个连通块里。我们想到使用并查集来维护。

我们可以先将所有有返回信息的节点打上标记， 然后按照顺序遍历依次取消标记，同时判断前后两个节点是否可以通过未打上标记的节点相互到达，如果结果为 false， 则输出 "No"。如果遍历完所有的节点依然合法，就输出 "Yes"。

上代码~

#include <cstdio>
#include <cstring> 
using namespace std;

int n, m, k, q;

inline char nc () {static char buf[1 << 21], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;}

inline int read () { 
    register int x(0),f(1); char ch = nc (); 
    while (ch > '9' || ch < '0') {if (ch == '-') f = ~f +1; ch = nc ();} 
    while (ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = nc ();} 
    return x * f;
}

int fath[200003];

int find (int now) {
    if (!(fath[now] ^ now)) return now;
    return fath[now] = find (fath[now]);
}  

int seq[200003];
bool vis[200003];

int head[200003], ent;

struct edge {
    int from, to, next;
}e[400003];

inline void add (int u, int v) {
    e[++ent] = (edge){u, v, head[u]};
    head[u] = ent;
}  

int main () {
    n = read (), m = read (), k = read (), q = read ();
    for (register int i(1); i <= m; ++i) {
        int u = read (), v = read ();
        add (u, v), add (v, u);
    }

    for (register int h(1); h <= q; ++h) {
        memset (vis, true, sizeof(vis)); //清空标记
        for (register int i(1); i <= k; ++i) seq[i] = read (), vis[seq[i]] = false;
        vis[seq[1]] = true;  //第一个有返回值的房间无论是什么，都一定是合理的
        for (register int i(1); i <= n; ++i) fath[i] = i;  //初始化
        for (register int i(1); i <= n; ++i) { 
            if (vis[i]) {
                for (register int j(head[i]); j; j = e[j].next) { //将未打上标记的点合并
                    int v = e[j].to;
                    if (vis[v]) {
                        if (fath[i] ^ fath[v]) {
                            fath[find(v)] = find (i);
                        }
                    }
                }
            }
        }
        bool flag = 1;
        for (register int i(2); i <= k; ++i) { //从第二个点开始顺序取消标记
            vis[seq[i]] = true;
            for (register int j(head[seq[i]]); j; j = e[j].next) {
                int v = e[j].to;
                if (vis[v]) {
                    fath[find(seq[i])] = find(v);
                }
            }
            if (fath[find(seq[i])] ^ fath[find(seq[i-1])]) {
                puts("No");
                flag = 0;
                break;
            }
        }
        if (flag) puts("Yes");
    }   
}