打卡信奥刷题（3678）用C++实现信奥题 P12274 [蓝桥杯 2024 国 Python B] 设计

P12274 [蓝桥杯 2024 国 Python B] 设计

题目描述

小蓝是 H 市的市长，她正在用设计软件规划 H 市的道路建设。

小蓝可以选定两个地区，用一条双向道路将这两个地区连接。由于预算等因素的动态变化，小蓝经常需要拆除一些已经建设好的道路，同时，她希望知道对于当前的两个地区，是否存在一条由多条道路组成的路径能够连接这两个地区。

输入格式

输入的第一行包含两个正整数 $n,m$，用一个空格分隔，其中 $n$ 表示地区个数，$m$ 表示操作次数。

接下来 $m$ 行，每行表示一个操作。对于每一行：

• $1$ $x_i$ $y_i$ 表示小蓝修建了一条连接地区 $x_i$ 与地区 $y_i$ 的双向道路。
• $2$ 表示小蓝拆除了当前 H 市中还未被拆除的最后修建的一条道路，如果当前城市中已经不存在道路，则小蓝不会进行任何操作。
• $3$ $x_i$ $y_i$ 表示小蓝希望知道地区 $x_i$ 与地区 $y_i$ 是否连通，即是否存在一条由多条道路组成的路径能够连接这两个地区。

输出格式

对于每个操作 $3$ 输出 Yes 或 No，其中 Yes 表示连通，No 表示不连通。

输入输出样例 #1

输入 #1

2 5
3 1 2
1 1 2
3 1 2
2
3 1 2

输出 #1

No
Yes
No

输入输出样例 #2

输入 #2

3 8
1 1 2
1 1 3
1 2 3
2
3 2 3
2
3 1 2
3 2 3

输出 #2

Yes
Yes
No

说明/提示

评测用例规模与约定

• 对于 $50\%$ 的评测用例，$n,m\le 3000$。
• 对于所有评测用例，$1\le n,m\le 300000$，$1\le x_i,y_i\le n$，$x_i\ne y_i$。

C++实现

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10;
int n, m;
int fa[MAXN], siz[MAXN];
stack<int> st;
int find(int x){
if(fa[x] != x) return find(fa[x]);
return fa[x];
}
void merge(int x, int y){
int r1 = find(x), r2 = find(y);
if(r1 == r2)
return st.push(0), void();//压入 0 表示冗余边
if(siz[r1] < siz[r2])
swap(r1, r2);
fa[r2] = r1, siz[r1] += siz[r2], st.push(r2);
}
void del(){
if(!st.size()) return;
int u = st.top(); st.pop();
if(u == 0) return;
siz[fa[u]] -= siz[u], fa[u] = u;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++)
fa[i] = i, siz[i] = 1;
for(int que = 1, opt, x, y; que <= m; que++){
cin >> opt;
if(opt == 1) cin >> x >> y, merge(x, y);
else if(opt == 2)
del();
else
cin >> x >> y, cout << (find(x) == find(y) ? "Yes" : "No") << '\\n';
}
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容