2026.3.27 作业 - # AT_abc420_e [ABC420E] Reachability Query

题目描述

给定一个有 \(N\) 个顶点且没有边的无向图。
顶点编号为 \(1,2,\dots,N\)，初始时所有顶点均为白色。
你需要处理共 \(Q\) 个如下三种类型的操作：

• 类型 \(1\)：在顶点 \(u\) 和 \(v\) 之间添加一条无向边。
• 类型 \(2\)：如果顶点 \(v\) 是白色，则将其变为黑色；如果是黑色，则将其变为白色。
• 类型 \(3\)：判断从顶点 \(v\) 出发，经过若干条边（可以为零条）是否能够到达某个黑色顶点；如果可以，输出 Yes，否则输出 No。

输入格式

输入由标准输入给出，格式如下：

\(N\) \(Q\)
\(\rm{Query}_1\)
\(\rm{Query}_2\)
\(\vdots\)
\(\rm{Query}_Q\)

其中 \(\rm{Query}_i\) 表示第 \(i\) 个操作。

类型 \(1\) 操作格式如下：

1 \(u\) \(v\)

类型 \(2\) 操作格式如下：

2 \(v\)

类型 \(3\) 操作格式如下：

3 \(v\)

输出格式

对于每个类型 \(3\) 的操作，输出如下结果：

• 如果从顶点 \(v\) 出发经过若干条边（可以为零条）能够到达某个黑色顶点，输出 Yes；
• 否则输出 No。

输入输出样例 #1

输入 #1

5 12
3 2
2 2
3 2
1 2 5
1 3 4
3 4
3 5
1 4 5
1 1 3
3 1
2 2
3 1

输出 #1

No
Yes
No
Yes
Yes
No

说明/提示

样例解释 1

在本输入中，图初始有五个顶点且没有边。
本输入包含 \(12\) 个操作。

• 第 1 个操作为 3 2。
  • 此时无法从顶点 \(2\) 出发到达任何黑色顶点，因此输出 No。
• 第 2 个操作为 2 2。
  • 顶点 \(2\) 是白色，将其变为黑色。
• 第 3 个操作为 3 2。
  • 此时可以从顶点 \(2\) 出发到达黑色顶点 \(2\)，因此输出 Yes。
• 第 4 个操作为 1 2 5。
  • 在顶点 \(2\) 和 \(5\) 之间添加一条边。
• 第 5 个操作为 1 3 4。
  • 在顶点 \(3\) 和 \(4\) 之间添加一条边。
• 第 6 个操作为 3 4。
  • 此时无法从顶点 \(4\) 出发到达任何黑色顶点，因此输出 No。
• 第 7 个操作为 3 5。
  • 此时可以从顶点 \(5\) 出发到达黑色顶点 \(2\)，因此输出 Yes。
• 第 8 个操作为 1 4 5。
  • 在顶点 \(4\) 和 \(5\) 之间添加一条边。
• 第 9 个操作为 1 1 3。
  • 在顶点 \(1\) 和 \(3\) 之间添加一条边。
• 第 10 个操作为 3 1。
  • 此时可以从顶点 \(1\) 出发到达黑色顶点 \(2\)，因此输出 Yes。
• 第 11 个操作为 2 2。
  • 顶点 \(2\) 是黑色，将其变为白色。
• 第 12 个操作为 3 1。
  • 此时无法从顶点 \(1\) 出发到达任何黑色顶点，因此输出 No。

数据范围

• 所有输入均为整数。
• \(1 \le N \le 2 \times 10^5\)
• \(1 \le Q \le 6 \times 10^5\)
• 类型 \(1\) 操作满足以下条件：
  • \(1 \le u < v \le N\)
  • 对于每个操作，\(u\) 和 \(v\) 之间的边此前未被添加过。
• 类型 \(2,3\) 操作满足以下条件：
  • \(1 \le v \le N\)

题解

动态加边，维护点的可达性问题，可以用集合来维护。

#include <iostream>
using namespace std;
const int MaxN=2e5+2;
int n,Q,Fa[MaxN],cnt[MaxN],col[MaxN];
int GetFa(int k) {if (k==Fa[k]) return k;return Fa[k]=GetFa(Fa[k]);
}
void Merge(int x,int y) {int fx=GetFa(x);int fy=GetFa(y);if (fx!=fy) {Fa[fy]=fx; cnt[fx]+=cnt[fy];cnt[fy]=0;}
}
int main(){cin>>n>>Q;for (int i=1;i<=n;i++) Fa[i]=i;while (Q--) {int k,u,v;scanf("%d",&k);if (k==1) {scanf("%d%d",&u,&v);Merge(u,v);}if (k==2) {scanf("%d",&v);col[v]=1-col[v];int fx=GetFa(v); if (col[v]==0) cnt[fx]--;else cnt[fx]++;}if (k==3) {scanf("%d",&v);int fx=GetFa(v);if (cnt[fx]>0)cout<<"Yes\n";else cout<<"No\n";}}return 0;
}