0x41 并查集

程序自动分析

题意：

一些变量，之间是相等与不相等关系。询问所有约束条件是否可以同时满足

解析：

并查集。并查集维护相等的变量，对于不相等变量，检查是否在在同一并查集里。注意离散化

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e6+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int n;
int fa[maxn];
struct query{int a, b, op, id;bool operator < (const query &b) const{return op > b.op;}
}q[maxn];
vector<int> t;
void init(int MAX){for(int i = 1; i <= MAX; i++)fa[i] = i;
}
int find(int x){return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
}
void merge(int x, int y){int fx = find(x);int fy = find(y);if(fx != fy){fa[fx] = fy;}
}
void solve(){cin >> n;t.clear();for(int i = 1; i <= n; i++){cin >> q[i].a >> q[i].b >> q[i].op;q[i].id = i;t.push_back(q[i].a);t.push_back(q[i].b);}sort(t.begin(), t.end());t.erase(unique(t.begin(), t.end()), t.end());for(int i = 1; i <= n; i++){q[i].a = lower_bound(t.begin(), t.end(), q[i].a) - t.begin()+1;q[i].b = lower_bound(t.begin(), t.end(), q[i].b) - t.begin()+1;}init(n << 1);sort(q+1, q+1+n);for(int i = 1; i <= n; i++){if(q[i].op == 1){merge(q[i].a, q[i].b);}else if(q[i].op == 0){int fx = find(q[i].a);int fy = find(q[i].b);if(fx == fy){cout << "NO" << endl;return;}}}cout << "YES" << endl;return;
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int T;cin >> T;while(T--)solve();return 0;
}

银河英雄传说

题意：

一些船，一开始每艘船单独一列。

两种操作：

• 将某一船所在列接到另一列的尾部
• 询问两艘船在同一列中之间有多少艘船

解析：

带权并查集。$dis[x]$ 为 $x$ 与 $fa[x]$ 之间的边权。

对于 $find$ 函数，将 $dis[x]$ 修改为到根节点路径上的边权和

对于 $merge$ 函数，如果将 $x$列 接到 $y$ 列后，$dis[x]=size[y]$，所以需要维护每个并查集的大小

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 3e4+10;
const int INF = 0x3f3f3f3f;
const int MAX = 3e4;
typedef pair<int, int> pii;int fa[maxn], dis[maxn], siz[maxn];
int find(int x){if(x != fa[x]){int t = fa[x];fa[x] = find(fa[x]);dis[x] += dis[t];siz[x] = siz[fa[x]];}return fa[x];
}
void merge(int x, int y){int fx = find(x);int fy = find(y);if(fx != fy){dis[fx] = dis[fy] + siz[fy];siz[fy] += siz[fx];siz[fx] = siz[fy];fa[fx] = fy;}
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int T, x, y;char op;cin >> T;for(int i = 1; i <= MAX; i++)fa[i] = i, siz[i] = 1;while(T--){cin >> op >> x >> y;if(op == 'M')merge(x, y);else if(op == 'C'){int fx = find(x);int fy = find(y);if(fx != fy)cout << -1 << endl;else if(x != y)cout << abs(dis[x]-dis[y])-1 << endl;elsecout << 0 << endl;}}return 0;
}

奇偶游戏

题意：

给定01序列 $s$。依次给定序列满足的条件 $(l,r,t)$ 表示 $s[l...r]$ 中 1 的个数是奇数还是偶数。
询问最后一个不产生矛盾的条件。

解析：

带权并查集。

已知 $s[l...r]$ 中1的个数的奇偶性，前缀和的思想，可以得到 $s[\mathrm{1...}l-1]$ 与 $s[\mathrm{1...}r]$ 的1的个数奇偶性是否相同。

权值 $val[x]$ 表示 $x$ 与 $fa[x]$ 奇偶性是否相同，0为相同，1为不同。

路径压缩的时候，$val[x]$ 的值为路径上权值的异或。

两个集合合并的时候，自己和自己的奇偶性一定相同，所以 $val[fa[x]]=val[x]\oplus val[y]\oplus w$，$w$ 为 $x,y$ 的奇偶性是否相同。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int fa[maxn], val[maxn];
struct node{int l, r, t;
}q[maxn];
vector<int> t;
int n, m;
string s;int find(int x){if(x != fa[x]){int rt = find(fa[x]);val[x] ^= val[fa[x]];fa[x] = rt;}return fa[x];
}
void merge(int x, int y, int w){int fx = find(x);int fy = find(y);if(fx != fy){fa[fx] = fy;val[fx] = val[x] ^ val[y] ^ w;}
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1; i <= m; i++){cin >> q[i].l >> q[i].r >> s;q[i].l--;if(s == "oven")q[i].t = 0;else if(s == "odd")q[i].t = 1;t.push_back(q[i].l);t.push_back(q[i].r);}sort(t.begin(), t.end());t.erase(unique(t.begin(), t.end()), t.end());n = t.size();for(int i = 1; i <= m; i++){q[i].l = lower_bound(t.begin(), t.end(), q[i].l)-t.begin()+1;q[i].r = lower_bound(t.begin(), t.end(), q[i].r)-t.begin()+1;}for(int i = 1; i <= n; i++)fa[i] = i, val[i] = 0;for(int i = 1; i <= m; i++){int fx = find(q[i].l);int fy = find(q[i].r);if(fx == fy){if(val[q[i].l]^val[q[i].r] != q[i].t){cout << i-1 << endl;return 0;}}elsemerge(q[i].l, q[i].r, q[i].t);}cout << m << endl;return 0;
}

食物链

题意：

三类动物 $A,B,C$ , $A$ 吃 $B$ ，$B$ 吃 $C$ ，$C$ 吃 $A$。

$n$ 个动物，和 $k$ 句话。每句话有两种描述：$X$ 和 $Y$ 是同类；$X$ 吃 $Y$。

如果某一句话与前边真话冲突，则是假话，询问假话数目

解析：

用 $3$ 倍并查集存关系，一倍存本身，二倍存食物，三倍存天敌

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 2e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;struct DSU{vector<int> fa;vector<int> rank;DSU(int n) : fa(n), rank(n){for(int i = 1; i <= n; i++)fa[i] = i;}int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}void merge(int x, int y){int fx = find(x);int fy = find(y);if(rank[fx] < rank[fy])fa[fx] = fy;else{fa[fy] = fx;if(rank[fx] == rank[fy])rank[fx]++;}}};
//1倍本身 2倍食物 3倍天敌 
int n, k, ans;
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> k;DSU dsu(3*n);int op, x, y;for(int i = 1; i <= k; i++){cin >> op >> x >> y;if(x > n || y > n){ans++;continue;}if(op == 1){if(dsu.find(x)==dsu.find(y+n) || dsu.find(x)==dsu.find(y+2*n)){ans++;continue;}dsu.merge(x, y);dsu.merge(x+n, y+n);dsu.merge(x+2*n, y+2*n);}else{if(x == y){ans++;continue;}if(dsu.find(x)==dsu.find(y) || dsu.find(x+2*n)==dsu.find(y)){ans++;continue;}dsu.merge(x, y+2*n);dsu.merge(x+n, y);dsu.merge(x+2*n, y+n);}}cout << ans << endl;return 0;
}