首页 > 代码库 > HLJU 1105 cpc 喵喵的拆分集合 (并查集的逆向操作)
HLJU 1105 cpc 喵喵的拆分集合 (并查集的逆向操作)
1105: 喵喵的拆分集合
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 37 Solved: 8
[Submit][Status][Web Board]
Description
众所周知,DoubleQ是DS(Data Structure)粉,她最爱DS了。现在她要实现一个神奇的DS,支持下列两个操作:
-删除某条边,表示为”D x”,即为删除第x条边
-查询两点是否属于一个集合,表示为”Q a b”,即为查询节点a与节点b是否在一个集合内,若在同一个集合内,输出”Yes”,否则输出”No”(输出不包括引号)
n<=100000,m<=100000,q<=100000
Input
多组数据。
对于每组数据,第一行包括三个正整数,分别代表数据结构中节点的个数n,边数m,操作数q
接下来的m行代表第i条边(从1开始),第i条边连接u和v两个顶点(无重边,无自环)
再接下来的q行每行包括一个格式如题描述操作
Output
对于每一个查询,输出包括一行,表示查询结果,即如果两点属于同一个集合输出”Yes”,否则输出”No”。
Sample Input
5 4 6
1 2
2 3
4 5
1 3
Q 1 2
D 1
Q 1 2
Q 3 4
D 2
Q 1 2
Sample Output
Yes
Yes
No
No
解析:逆向处理。由于删边不好实现,我们可以换个思路。先把所有操作保留下来,然后再倒序执行各操作,这样的话,删边就相当于先不把这条边加进去,然后再按照倒序执行各个操作即可。
AC代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 100000 + 10; typedef struct node{ int a, b; }edge; edge e[maxn], q[maxn]; int del[maxn], is_d[maxn]; bool s[maxn]; int par[maxn]; //father[]数组 char op[maxn][4]; //保存操作 inline int getpar(int x){ return x == par[x] ? x : par[x] = getpar(par[x]); } inline void unin(int x, int y){ int a = getpar(x), b = getpar(y); if(a != b) par[a] = b; } int main(){ #ifdef sxk freopen("in.txt", "r", stdin); #endif // sxk std::ios::sync_with_stdio(false); std::cin.tie(0); int n, m, k; while(scanf("%d%d%d", &n, &m, &k)!=EOF){ memset(is_d, 0, sizeof(is_d)); memset(s, false, sizeof(s)); memset(e, 0, sizeof(e)); memset(q, 0, sizeof(q)); memset(del, 0, sizeof(del)); for(int i=1; i<=n; i++){ par[i] = i; } for(int i=1; i<=m; i++){ scanf("%d%d", &e[i].a, &e[i].b); } int fo = 0, foo = 0; for(int i=1; i<=k; i++){ scanf("%s", &op[i]); if(op[i][0] == 'Q'){ foo ++; scanf("%d%d", &q[foo].a, &q[foo].b); } else { fo ++; scanf("%d", &del[fo]); is_d[ del[fo] ] = 1; } } for(int i=1; i<=m; i++){ if(!is_d[i]) unin(e[i].a, e[i].b); } int cnt = foo; for(int i=k; i>0; i--){ if(op[i][0] == 'Q'){ if(getpar( q[cnt].a ) == getpar( q[cnt].b )) s[cnt] = true; else s[cnt] = false; cnt --; } else{ unin(e[ del[fo] ].a, e[ del[fo] ].b); fo --; } } for(int i=1; i<=foo; i++) printf("%s\n", s[i] == true ? "Yes" : "No"); } return 0; }
HLJU 1105 cpc 喵喵的拆分集合 (并查集的逆向操作)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。