并查集扩展

普通并查集

例题:

1.洛谷P1197 星球大战

链接:

[P1197JSOI2008] 星球大战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

类型:

普通并查集+反向加点

解析:

正面删边很难,考虑反向求解,先求删完所有要求点的所有连通块数量,然后再一个一个加入,将问题简化

代码:

const int N = 400005;struct edges{int v,ne;}e[N << 1];int h[N],idx = 0;void add(int u,int v){e[idx] = {v,h[u]};h[u] = idx++;}int f[N];int fd(int x){if(x==f[x]) return x;return f[x] = fd(f[x]);}int vis[N],ans[N];int n,m;void solve(){memset(h,-1,sizeof h);cin >> n >> m;for(int i = 1;i<=n;i++) f[i] = i;vector<int> b;for(int i = 1;i<=m;i++){int u,v;cin >> u >> v;u++,v++;add(v,u);add(u,v); }int k;cin >> k;int res = n - k;for(int i = 0;i<k;i++){int t;cin >> t;t++;vis[t] = 1;b.push_back(t);}for(int i = 1;i<=n;i++){if(vis[i]) continue;for(int j = h[i];~j;j=e[j].ne){int v = e[j].v;if(vis[v]) continue;if(f[fd(i)] != f[fd(v)]){res--;f[fd(i)] = f[fd(v)];}}}ans[k+1] = res;for(int i = k - 1;i >= 0;i--){vis[b[i]] = 0;res++;for(int j = h[b[i]];~j;j=e[j].ne){int v = e[j].v;if(vis[v]) continue;if(f[fd(b[i])] != f[fd(v)]){res--;f[fd(b[i])] = f[fd(v)];}}ans[i + 1] = res;}for(int i = 1;i<=k+1;i++){cout << ans[i] << endl;}}

2.洛谷P1955 程序自动分析

链接:

[P1955NOI2015] 程序自动分析 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

类型:

普通并查集+离散化

解析:

普通并查集判断是否矛盾,数据大进行离散化

代码:

const int N = 200005;struct DSU { vector<int> f; DSU(){} DSU(int n) { init(n); } void init(int n) { f.resize(n); iota(f.begin(), f.end(), 0); } int fd(int x) { if(f[x]==x) return x; return f[x] = fd(f[x]); } bool same(int x, int y) { return fd(x) == fd(y); } bool mg(int x, int y) { x = fd(x); y = fd(y); if (x == y)return false; f[y] = x; return true; }};int gt_idx(vector<int>& a,int i){int t = lower_bound(a.begin(),a.end(),i) - a.begin() + 1;return t;}void solve(){int n;cin >> n;vector<int> v1;vector<pair<int,int>> ys;vector<pair<int,int>> ns;vector<int> a;for(int i = 0;i < n;i++){int u,v,op;cin >> u >> v >> op;if(op==1){ys.push_back({u,v});}else{ns.push_back({u,v});}a.push_back(u);a.push_back(v);}sort(a.begin(),a.end());a.erase(unique(a.begin(),a.end()),a.end());int sz = a.size();DSU d(sz + 1);for(auto &[u,v]:ys){d.mg(gt_idx(a,u),gt_idx(a,v));}for(auto &[u,v]:ns){if(d.fd(gt_idx(a,u)) == d.fd(gt_idx(a,v))){cout <<"NO" << endl;return;}}cout <<"YES" << endl;}

带权并查集

例题:

1.洛谷P2024 食物链

链接:

[P2024NOI2001] 食物链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

类型:

带权并查集

解析:

维护%3关系,考虑合并时候维护集合关系,在同类时候d[u] - d[v]在%3意义下一定是0,x吃y那么一定是1,题目无需考虑2的情况,因为没有设置y吃x的正确性

代码:

const int N = 200005;int f[N],d[N];int n,m;int fd(int x){if(x!=f[x]){int t = f[x];f[x] = fd(f[x]);d[x] += d[t];} return f[x];}int calc(int x,int y){return ((x-y)%3 + 3)%3;}void merge(int x,int y,int v){int px = fd(x),py = fd(y);f[px] = py;d[px] = d[y] - d[x] + v;}void solve(){cin >> n >> m;iota(f,f+n+1,0);int cnt = 0;while(m--){int u,v,op;cin >> op >> u >> v;if(u>n||v>n){cnt++;continue;}if(op==1){if(fd(u)==fd(v) && calc(d[u],d[v]) != 0){cnt++;continue;}//d[v] = d[u] + d[fd(u)]//d[fd[u]] = d[v] - d[u]if(fd(u)!=fd(v)) merge(u,v,0);}else{if(fd(u)==fd(v) && calc(d[u],d[v]) != 1){cnt++;continue;}//d[v] = d[u] - 1 + d[fd(u)]//d[fd[u]] = d[v] - d[u] + 1if(fd(u)!=fd(v)) merge(u,v,1);}}cout << cnt << endl;}

2.洛谷P1196 银河英雄传说

链接:

[P1196NOI2002] 银河英雄传说 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

类型:

带权并查集

解析:

维护两个变量,一个是集合大小,一个是元素到根的距离,然后操作即可

代码:

const int N = 200005;int sz[N],d[N],f[N];void init(){for(int i = 0; i < N - 1;i++){f[i] = i;sz[i] = 1;}}int fd(int x){if(f[x]!=x){int t = f[x];f[x] = fd(f[x]);d[x] += d[t];}return f[x];}void merge(int x,int y){int px = fd(x),py = fd(y);f[px] = py;d[px] = sz[py];sz[py] += sz[px];}void solve(){int q;init();cin >> q;while(q--){int x,y;char op;cin >> op >>x >> y;if(op=='C'){if(fd(x)!=fd(y)){cout <<-1<<endl;}else{cout << abs(d[x]-d[y]) - 1 << endl;}}else{merge(x,y);}}}

3.洛谷P5937 Parity Game

链接:

[P5937CEOI1999] Parity Game - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

类型:

带权并查集

解析:

前缀和思想,合并 y 与 x - 1 判断奇偶性即可

代码:

const int N = 200005;int n,q;int idx = 0;map<int,int> h;int gt(int x){if(h.count(x)) return h[x];h[x] = ++idx;return idx;}int d[N],f[N];int fd(int x){if(f[x] != x){int t = f[x];f[x] = fd(f[x]);d[x] += d[t];}return f[x];}void merge(int x,int y,int v){int px = fd(x),py = fd(y);f[px] = py;d[px] = d[y] - d[x] + v;}int calc(int x,int y){return ((d[x] - d[y])%2 + 2)%2;}void solve(){cin >> n >> q;int res = q;for(int i = 0;i<N;i++) f[i] = i;int id = 0;while(q--){int x,y;++id;string op;cin >> x >> y >> op;if(x==y&&op=="even"){res = id-1;break;}x = gt(x - 1);y = gt(y);if(op=="even"){if(fd(x)==fd(y)){if(calc(x,y) == 1){res = id - 1;break;}}else{merge(x,y,0);}}else{if(fd(x)==fd(y)){if(calc(x,y) == 0){res = id - 1;break;}}else{merge(x,y,1);}}}cout << res << endl;}

扩展域并查集

例题:

1.洛谷P1525 关押罪犯

链接:

[P1525NOIP2010 提高组] 关押罪犯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

类型:

扩展域并查集 + 带权并查集

解析:

方法一(扩展域并查集):

• 两个集合,从大到小排序,考虑将敌对两个人分成两个集合,并且扩展域合并,敌人的敌人是朋友,就是设x有两个敌人 y z, 那么 z 与 x+n 建边, x +n 与 y 建边,通过 x+n这个虚点去连接应该在一个集合中的y与z,如果在同一集合,并且是敌对,那么直接输出即可

方法二(带权并查集):

• 从大到小排序,避免前面的数在一个监狱,将两个集合合并起来,并且赋权值为1代表两个数不在同一监狱,于是在后面我们可以判断,如果两个数之前已经合并过并且mod操作位0代表,这两个集合一定要在一个监狱中,那么直接输出w,(否则,w会更大)

代码:

方法一:

int n,m;struct qs{int u,v,w;bool operator<(const qs& q1)const{return w > q1.w;}}; struct DSU { vector<int> f, sz; DSU(){} DSU(int n) { init(n); } void init(int n) { f.resize(n); iota(f.begin(), f.end(), 0); sz.assign(n, 1); } int fd(int x) { if(f[x]==x) return x; return f[x] = fd(f[x]); } bool mg(int x, int y) { x = fd(x); y = fd(y); if (x == y)return false; f[y] = x; return true; }};void solve(){cin >> n >> m;DSU d(2*(n+1));vector<qs> q;for(int i = 0; i < m;i++){int u,v,w;cin >> u >> v >> w;q.push_back({u,v,w});}sort(q.begin(),q.end());for(int i = 0;i < q.size();i++){int u = q[i].u,v = q[i].v,w = q[i].w;if(d.fd(u) == d.fd(v)){cout << w <<endl;return;}d.mg(u,v+n);d.mg(u+n,v);}cout << 0 << endl;}

方法二:

struct qs{int u,v,w;bool operator<(const qs &t)const{return w > t.w;};};int f[N],d[N];int n,m;int fd(int x){if(x!=f[x]){int t = f[x];f[x] = fd(f[x]);d[x] += d[t];} return f[x];}int calc(int x,int y){return ((x-y)%2 + 2)%2;}void merge(int x,int y){int px = fd(x),py = fd(y);f[px] = py;d[px] = d[y] - d[x] + 1;}void solve(){cin >> n >> m;int q = m;vector<qs> a;iota(f,f+n+1,0);while(q--){int u,v,w;cin >> u >> v >> w;a.push_back({u,v,w});}sort(a.begin(),a.end());for(int i = 0; i < m;i++){int u = a[i].u,v = a[i].v,w = a[i].w;if(fd(u)==fd(v)){if(calc(d[u],d[v]) == 0){cout << w << endl;return;}}else{merge(u,v);}}cout << 0 <<endl;}