网站的公关和广告活动怎么做,婚庆网站开发要达到的目标,深圳住房和建设局网站认租申请,免费制作网站平台并查集简介
并查集是一种可以动态维护若干个不重叠的结合#xff0c;并支持合并与查询的数据结构 并查集是一种树状的数据结构#xff0c;可以用于维护传递关系以及联通性。 并查集有两种操作#xff1a;
find#xff1a;查询一个元素属于哪个集合merge:合并两个集合
模…并查集简介
并查集是一种可以动态维护若干个不重叠的结合并支持合并与查询的数据结构 并查集是一种树状的数据结构可以用于维护传递关系以及联通性。 并查集有两种操作
find查询一个元素属于哪个集合merge:合并两个集合
模板
find函数
int find(int x)
{if(x fa[x]) return x;reutnr fa[x] find(fa[x]);
}merge函数
void merge(int x, int y)
{int px find(x), py find(y);if(px ! py) fa[px] py;
}模板题
村村通 对于这道题我们只需要求连通块的数量然后将这几个联通快看成点联通n个点需要n-1条边
#include iostream
#include cstringusing namespace std;
const int N 1010;
int p[N], st[N];int find(int x)
{if(x p[x]) return x;return p[x] find(p[x]);
}int main()
{// freopen(1.in, r, stdin);while(1){memset(st, 0, sizeof st);int n, ans 0;scanf(%d, n);if(n 0) return 0;else{int m; scanf(%d, m);for(int i 1; i n; i) p[i] i;for(int i 0; i m; i){int x, y; scanf(%d%d, x, y);int a find(x);int b find(y);if(a ! b) p[a] b;}//统计联通块的数量for(int i 1; i n; i){int x find(i);if(!st[x]) ans , st[x] 1;;}cout ans - 1 endl;}}
}P1551 亲戚 亲戚的亲戚是亲戚亲戚这种关系具有传递性如果具有亲戚关系就将合并。
#include iostreamusing namespace std;const int N 5010;int p[N];
int n, m, t;int find(int x)
{if(x ! p[x]) p[x] find(p[x]);return p[x];
}int main()
{cin n m t;for(int i 1; i n; i) p[i] i;for(int i 0; i m; i){int a, b;cin a b;int fa find(a);int fb find(b);p[fa] fb;}for(int i 0; i t; i){int a, b;cin a b;int fa find(a);int fb find(b);if(fa ! fb) puts(No);else puts(Yes);}return 0;
}836. 合并集合
#include iostreamusing namespace std;const int N 1e510;int n,m;
int p[N];int find(int x)
{if(p[x] ! x ) p[x] find(p[x]);return p[x];
}int main(int argc, const char * argv[]) {scanf(%d%d,n,m);for(int i 0; i n; i ) p[i] i;while(m--){char op[2];int a,b;scanf(%s%d%d,op,a,b);if(op[0] M) p[find(a)] find(b);else{if(find(a) find(b)) coutYesendl;else puts(No);}}return 0;
}837. 连通块中点的数量 这道题目比前面的几道模板题目需要多维护一个信息在进行merge时我们需要将更新作为被添加枝的树的cnt 两个bug调了一个小时最后看了下评论区收获颇丰 1、合并两个集合时 如果没有按照下面的写法即省去这一步afind(a),bfind(b); 则合并根节点的顺序与更新更新集合得顺寻不能互换 必须要先把原来根节点中元素的数量加到所要合并的 根节点上去再把根节点合并 afind(a),bfind(b); cnt[b]cnt[a]; p[a]b; 2、路径压缩 一定不要忘记路径压缩不然会超时
#includebits/stdc.h
using namespace std;
const int N1e510;
int p[N],cnt[N];
int n,m;
int find(int x)
{if(p[x] ! x) p[x] find(p[x]);return p[x];
}
int main()
{cin.tie(0);cinnm;for(int i1;in;i) {p[i]i;cnt[i]1;}while(m--){string str;int a,b;cinstr;if(strC){cinab;if(find(a)!find(b)) {afind(a),bfind(b);cnt[b]cnt[a];p[a]b;}}else if(strQ1){cinab;if(find(a)find(b)) coutYesendl;else coutNoendl;}else{cina;coutcnt[find(a)]endl;}}return 0;
}边带权并查集
推导部分和 这道题的是带边权并查集的应用比较难想到的是建图 对于每个区间l, rk, 我们可以由前缀和s[r] - s[l - 1] k我们从r连一条l-1的边
#include iostreamusing namespace std;
typedef long long LL;
const int N 1e5 10;
//p[N]数组用来做并查集
int p[N], n, m, q;
//s[N]数组是当前点到根结点的权值和也是前缀和
LL s[N];//并查集的查询操作带路径压缩
int find(int x)
{if(x p[x]) return x;else{int t find(p[x]);s[x] s[p[x]];p[x] t;return t;}
}int main()
{// freopen(1.in, r, stdin);cin n m q;for(int i 1; i n; i) p[i] i;for(int i 0; i m; i){int l ,r;LL k; cin l r k;int t1 find(l - 1), t2 find(r);if(t1 ! t2){p[t2] t1;s[t2] s[l - 1] - s[r] k;}}while(q --){int l, r;cin l r;int t1 find(l - 1), t2 find(r);if(t1 ! t2) puts(UNKNOWN);else printf(%lld\n, s[r] - s[l - 1]);}return 0;
}P1196 [NOI2002] 银河英雄传说 这道题目比较特殊是每个集合是一条链一条链也是一棵树不过是树的特殊形态我们可以把每一列看作一个集合用并查集去维护另外题目中需要知道两个点之间的点有多少个这里我们就还需要额外维护每个点到根节点路径上的权值因为我们这里的并查集已经进行优化即使用了路径压缩并且边权都是1所以在维护每个点到根节点的路径上的权值时我们还需要用到一个集合中元素的个数也就是还需要额外维护集合中元素个数。 综上我们需要额外维护两个信息
d[x]:表示x到根节点的边权求和size[x]:表示以x为根的子树中节点数量
#include bits/stdc.h
#define ls p1
#define rs p1|1
#define PII pairint, int
#define ll long long
#define ull unsigned long long
#define endl \n
#define db double
using namespace std;const int N 30010;
int fa[N], d[N], size[N],t;void init()
{for(int i 1; i N - 1; i) fa[i] i, size[i] 1;
}int find(int x)
{if(x fa[x]) return x;int root find(fa[x]);d[x] d[fa[x]];return fa[x] root;
}void merge(int x, int y)
{int px find(x), py find(y);if(px py) return;fa[px] py;d[px] size[py];size[py] size[px];
}void solve()
{cin t;init();for(int i 1; i t; i){char op;int x, y;cin op x y;if(op M) merge(x, y);else{int px find(x), py find(y);if(px ! py) cout -1 endl;else cout abs(d[x] - d[y]) - 1 endl; } }
}int main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen(1.in, r, stdin);
// cin t;
// while(t --) solve(); return 0;
}并查集的拓展域
P2024 [NOI2001] 食物链 这是一道并查集的拓展域的题目也可以用带权并查集去做 普通并查集维护的是不相交集合是一种传递性的关系如亲戚的亲戚是亲戚 天敌的天敌是食物是一种环形的关系 我们如果用拓展域来解决这道题目的话可以用3个并查集来维护3种关系第一种是同类关系第二种是食物关系第三种是天敌 我们不用真开三个并查集我们可以将三个并查集开到一个数组里下标的范围代表不同的集合
#include iostreamusing namespace std;
const int N 5e4 10;
int p[N * 3], ans, k, n;//1--n代表x的同类n 1 -- 2n代表x的食物 2n 1 -- 3n代表x的天敌
int find(int x)
{if(x p[x]) return x;return p[x] find(p[x]);
}
void merge(int x, int y)
{int px find(x), py find(y);p[py] px;
}
int main()
{cin n k;for(int i 1; i 3 * n; i) p[i] i;for(int i 0; i k; i){int d, x, y;scanf(%d%d%d, d, x, y);if(x n || y n) ans ;//x、y是同类else if(d 1){//如果根据前面的信息我们可以知道y在x的食物域//或者y在x的天敌域中说明这句话是假话if(find(x n) find(y) || find(x n n) find(y)) ans ;//如果根据前面的信息不能判断这句话是错误的那么就讲这句话//当成对的并且更新x的三个域else{//y在x的同类域中merge(x, y);//y的食物和x的食物是同类merge(x n, y n);//y的天敌和x的天敌是同类merge(x n n, y n n);}}//如果x吃yelse{//若果y在x的同类域或者y在x的天敌域说明这句话是假话if(find(x) find(y) || find(x n n) find(y)) ans ;//这句话是真话就更新x的三个域else{//y在x的食物域中merge(x n, y);//y的食物是x的天敌merge(x n n, y n);//y的天敌是x的同类merge(x, y n n);}}}cout ans endl;return 0;
}例题团伙
#include iostream
using namespace std;
const int N 2010;
int p[N];
bool st[N];
int find(int x)
{if(p[x] x) return p[x];return p[x] find(p[x]);
}
void merge(int x, int y)
{int px find(x), py find(y);if(px ! py) p[px] py;
}int main()
{// freopen(1.in, r, stdin);int n, m;scanf(%d%d, n, m);for(int i 1; i 2 * n; i) p[i] i;for(int i 0; i m; i){char op; int x, y;cin op x y;if(op F){merge(x, y);// merge(x n, y n);}else{merge(x n, y);merge(x, y n);}}// for(int i 1; i n; i) cout i find(i) endl; int cnt 0;for(int i 1; i n; i)if(!st[find(i)]){cnt ;st[find(i)] 1;}cout cnt endl;return 0;
}P5937 [CEOI1999] Parity Game
题目的具体思路如下考虑一段连续区间的1个数的奇偶可以转化为考虑考虑两个端点前缀和的奇偶性上分为两种情况如果[l, r]区间内1的个数为偶数说明sum[r]和sum[l - 1]包含1的个数的奇偶性相同反之若为奇数则两个包含1的个数的奇偶性相反我们知道奇偶性具有传递性这样我们就可以种类并查集来维护注意n的范围比较大但是实际的需要用到的点的个数是比较小的这里我们需要离散化一下。
#include bits/stdc.h
#define LL long long
using namespace std;const int N 1e4 10;
int p[N * 2 10], n, m, k;
mapint, intmp;
int b[N * 2];struct wy
{int l, r, op;
}q[N];int find(int x)
{if(x ! p[x]) p[x] find(p[x]);return p[x];
}void merge(int x, int y)
{int px find(x), py find(y);p[py] px;
}int query(int x)
{return lower_bound(b 1, b 1 k, x) - b;
}
void solve()
{scanf(%d%d, n, m);for(int i 1; i m; i){int l, r, op;char s[5];scanf(%d%d%s, l, r, s);if(s[0] e) op 1;else op 2;q[i] {--l, r, op};b[ k] l;b[ k] r;} sort(b 1, b 1 k);k unique(b 1, b 1 k) - (b 1);for(int i 1; i 2 * k; i) p[i] i;for(int i 1; i m; i){int l query(q[i].l), r query(q[i].r), op q[i].op;if(op 1) {if(find(l) find(r k) || find(r) find(l k)){printf(%d, i - 1);return;}else{merge(l, r);merge(l k, r k);}}else{if(find(l) find(r) || find(r k) find(l k)){printf(%d, i - 1);return;}else{merge(l, r k);merge(r, l k); }} }printf(%d, m);
}
int main()
{
// freopen(1.in, r, stdin);solve(); return 0;
}应用
P1955 [NOI2015] 程序自动分析
这道题目是相等关系相等关系也具有传递性明显我们可以用并查集来维护。 我们可以先对处理相等然后去查询不相等的是否在一个集合里面如果在一个集合里面则说明这样的点是不存在的。这道题目的数据的范围很大但实际用到的很少我们需要对数据进行离散化。
#include bits/stdc.h
#define LL long long
using namespace std;const int N 1e6 10;
int n, m, p[N], a[N], k, tot;
struct wy{int x, y, e;
}q[N];int find(int x)
{if(x ! p[x]) p[x] find(p[x]);return p[x];
} void merge(int x, int y)
{int px find(x), py find(y);p[py] px;
}void solve()
{scanf(%d, n);for(int i 1; i n; i){int x, y, e;scanf(%d%d%d, x, y, e);a[ tot] q[i].x x;a[ tot] q[i].y y;q[i].e e; }sort(a 1, a 1 tot);tot unique(a 1, a 1 tot) - a - 1;for(int i 1; i tot; i) p[i] i;for(int i 1; i n; i){q[i].x lower_bound(a 1, a tot 1, q[i].x) - a - 1;q[i].y lower_bound(a 1, a tot 1, q[i].y) - a - 1;if(q[i].e 1){merge(q[i].x, q[i].y);}}for(int i 1; i n; i){int x q[i].x;int y q[i].y;if(q[i].e 0 find(x) find(y)){puts(NO);return;}}puts(YES);
}int main()
{
// freopen(1.in, r, stdin);scanf(%d, k);while(k--) solve(); return 0;
}P1525 [NOIP2010 提高组] 关押罪犯 贪心并查集我们优先选择边权最大的罪犯首先查询他们是否已经在一个集合 如果不在分别将他们放进不同监狱集合如果在则说明我们已经找到了答案
#include bits/stdc.h
#define ls p1
#define rs p1|1
#define PII pairint, int
#define ll long long
#define ull unsigned long long
#define endl \n
#define db double
using namespace std;const int N 1e6 10, e 20010;struct wy
{int x, y, val;bool operator (const wy t) const{return t.val val;}
}a[N];int p[N 1];
int n, m;void init()
{for(int i 1; i N; i) p[i] i;
}int find(int x)
{if(x p[x]) return x;return p[x] find(p[x]);
}void merge(int x, int y)
{int px find(x), py find(y);if(px ! py) p[py] px;
}void solve()
{cin n m;for(int i 1; i m; i){int x, y, val; cin x y val;a[i] {x, y, val};}sort(a 1, a 1 m);init();for(int i 1; i m; i){int x a[i].x, y a[i].y, val a[i].val;int px find(x), py find(y);if(px py) {cout val endl;return;}else{merge(y n, x);merge(x n, y);}}cout 0 endl;
}
int main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen(1.in, r, stdin);
// cin t;
// while(t --) solve(); return 0;
}
