自动搬运

查看原文

来自洛谷，原作者为

	Froranzen 你没有那个实力，不要再欺骗自己了

搬运于2025-08-24 21:34:57，当前版本为作者最后更新于2020-12-09 16:23:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

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

我们可以先将所有有返回信息的节点打上标记， 然后按照顺序遍历依次取消标记，同时判断前后两个节点是否可以通过未打上标记的节点相互到达，如果结果为 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");
	}	
}