【数据结构与算法】并查集(数据结构与算法分析)

java8

帖子摘要：大家好我是白晨一个不是很能熬夜但是也想日更的人?。如果喜欢这篇文章点个赞关注一下白晨吧你的支持就是我最大的动力   文章目录 前言并查集定义及实例实现工程向实现算法向实现   相关例题合并集合连通块中......
$ n- _% `+ x2 j% }, \$ U
8 ^7 W7 E3 U6 N! m5 U大家好，欢迎来到Java吧（www.java8.com），交流、学习Java技术、获取Java资源无任何套路，今天说一说：“【数据结构与算法】并查集”

. r3 g7 Z' t  v! U- k' @
        
) d9 S4 _  i( n* i               
                    
4 ], X7 ]: k/ P' b1 S; s; H                        
                    
                    大家好我是白晨一个不是很能熬夜但是也想日更的人?。如果喜欢这篇文章点个赞关注一下白晨吧你的支持就是我最大的动力
4 g. k2 L# B; p( E: t

a47fdd9889d5450faef1c615e4673666.gif (2.72 MB, 下载次数: 0, 售价: 3 金钱)

2023-2-2 02:12 上传

点击文件名下载附件
a47fdd9889d5450faef1c615e4673666.gif

2 f  i5 F7 V# T, K3 O& a. S 文章目录
2 ]2 |& u0 `* P% B, R

前言

并查集

定义及实例

实现

工程向实现

算法向实现
   

相关例题

合并集合

连通块中点的数量

?食物链
  
  

后记
$ B- ^6 Q6 M6 M3 F& s
前言

$ A* x2 I! f* m4 S! B大家好我是白晨这次为大家带来的数据结构是

并查集
复制代码

这是一种能够快速合并两个集合以及快速查询两个元素是否在一个集合中时间复杂度在大量查询的情况下可以达到O(1)的数据结构由于实现思路简单代码短性质好经常会在算法题中用到。同时并查集也在与图相关的算法中出现过很多次例如最小生成树Kruskal算法就使用了并查集。

9 M* z! S+ o3 k' P# e; e$ ~

61fe38119607e93bf1dfa0b620493e38.gif (218.22 KB, 下载次数: 0, 售价: 6 金钱)

2023-2-2 02:12 上传

点击文件名下载附件
61fe38119607e93bf1dfa0b620493e38.gif

/ K8 |5 @" G. i' s* ]% F
7 o6 o3 S, u4 e  g; [并查集

定义及实例


  F* k1 g* S, p3 o" s 并查集 英文Disjoint-set data structure直译为不交集数据结构是一种数据结构 用于处理一些不交集 Disjoint sets一系列没有重复元素的集合的合并及查询问题。并查集支持如下操作

查询查询某个元素属于哪个集合通常是返回集合内的一个"代表元素"。这个操作是为了判断两个元素是否在同一个集合之中。
; s2 E8 h* D: s

合并将两个集合合并为一个。

% ?/ H( Y# |9 @. `+ F- D+ |
举个例子有

小明、小亮、小虎、小李、小王、小孙
复制代码

六个学生已知

小明
复制代码

和

小孙
复制代码

是同学

小王
复制代码

和

小明
复制代码

是同学

小亮
复制代码

和

小李
复制代码

是同学

小虎
复制代码

和

小孙
复制代码

是同学。
# X8 [+ ^6 @1 g( W% \) p

问

小虎
复制代码

和

小王
复制代码

是什么关系

小李
复制代码

和

小王
复制代码

是什么关系

ae39f222041d97bf936d832f816d840c.png (23.25 KB, 下载次数: 0, 售价: 4 金钱)

2023-2-2 02:12 上传

点击文件名下载附件
ae39f222041d97bf936d832f816d840c.png

! [, D5 y/ s; @" A按照常识我们可以把互为同学的学生划入同一个集合如果两个同学的名字在同一个集合中出现那么这两个人互为同学。反之两个人不是同学。
% M7 s% [* z% S
* A- n- l9 n" }5 y, A' E

e3e6cf4f961316d70f9acbe76f3b253a.png (22.04 KB, 下载次数: 0, 售价: 6 金钱)

2023-2-2 02:12 上传

点击文件名下载附件
e3e6cf4f961316d70f9acbe76f3b253a.png

观察上图

小虎
复制代码

和

小王
复制代码

是同学关系

小李
复制代码

和

小王
复制代码

不是同学关系。

上面就是并查集的简单应用并查集能够快速合并两个集合以及快速查询两个元素是否在一个集合中时间复杂度在大量查询的情况下可以达到O(1)。


实现
. s; ]- k/ T; K0 n! k: r0 `
  I3 P! _! y) U0 d* ^
0 R# p3 N7 z. q( x: L/ g$ L 并查集要实现的操作就两种——

合并
复制代码

和

查询
复制代码

只要抓住并查集的核心思路并查集的实现是非常简单的白晨给出两种实现方式作为参考一种是工程向的实现方式另一种是算法竞赛向的实现方式两种实现方式的思想是不变的重点是体会并查集的思想。
+ H2 L, p# D- o; ?- [% @& Q# k' Q

) d2 s1 N( I* t  e工程向实现

存储结构数组

初始化数组元素全部初始化为

-1
复制代码

。

存储数据根节点为负数其绝对值为集合中元素的个数孩子结点中存放父节点的下标。

class UnionFindSet
  v0 l6 p  N) [
{
. K$ ~1 z, J: N3 E8 E( F* ?: W: z
public:
) b" O. H5 v6 F* H# Q3 u
        // 默认全部都无父节点为-1
        UnionFindSet(size_t sz)
- Z$ ?2 C) h+ X$ n0 A7 n
                :_ufs(sz, -1)
( h, B; e; G3 h8 J
        {}
1 ^5 N, V( R/ Q$ B$ ~. N* p3 b% h
private:
        vector[i] _ufs; // 根节点为负数其绝对值为集合中元素的个数孩子结点中存放父节点的序号
" t7 B# f+ J) H3 s* M% _4 ]3 C, s
};
复制代码

查询
并查集最核心的操作就是查询元素集合的根如果两个元素集合的根相同说明两个元素在同一个集合中。子节点存放的是父节点的下标只需要向上查找就能找到根。
' p) v/ q6 J! O7 r$ V0 ]# D
& i) j9 v7 G! B5 D; S

2519025c7a5a49942b9efad78f9fd22a.png (56.56 KB, 下载次数: 0, 售价: 1 金钱)

2023-2-2 02:12 上传

点击文件名下载附件
2519025c7a5a49942b9efad78f9fd22a.png

1 V- s& X" `& S具体实现

; ~" W- V) \4 Y

// 核心代码查找一个子集的根
2 m  Z2 ?8 U% f$ E. v* w
int FindRoot(int x)
{
        int root = x;
        // 查找到结点权值为负的根
% b( i5 M9 F' G4 l& H" F' `
        while (_ufs[root] >= 0)
        {
                root = _ufs[root];
        }
& k" ?  q$ {" b% B* ^- ?. g
        return root;
}
复制代码

但是如果树的层数太高我们就无法保证O(1)的时间复杂度所以我们做一优化每查询一次将查询的节点到根的所有结点直接连接到根结点上。
: j( |# n7 p) j: x! m

// 核心代码查找一个子集的根
int FindRoot(int x)
{
/ X  z4 l) {# }, d; v
        int root = x;
        // 查找到结点权值为负的根
        while (_ufs[root] >= 0)
        {
/ i" p- a3 K. y0 B9 B5 S! n- D0 |: d" E
                root = _ufs[root];
7 r* X# f9 m6 [0 g( X
        }
        // 优化将被查找结点及路径上直接连接到根
* t5 u; V3 c9 m4 F
        int cur = x;
! h9 r' P7 g( z6 p( O8 H- [$ u4 I
        while (_ufs[cur] >= 0)
( p+ |. e4 X  _* S8 p# s+ G
        {
9 u, C( A0 f8 }+ v
                int parent = _ufs[cur];
                _ufs[cur] = root;
( D$ R3 j8 N3 a, e1 I3 Y  q/ O
                cur = parent;
0 s7 s& U" J- L: k& E! ~
        }
  R3 t$ G5 `8 c/ B
        return root;
6 N* \+ R. J( r! `2 r  n
}
7 j' f' [4 S& t0 J4 ^# e- _
复制代码

重复迭代的代码太长我们也可以使用递归实现两行代码完成查找+路径优化
' H, K! \" a/ J6 f8 f) T8 t* q

// 根结点查找 + 路径优化
int FindRoot(int x)
0 j9 c1 Z7 g2 ]- [# B' m& r9 ?
{
        if (_ufs[x] >= 0) _ufs[x] = FindRoot(_ufs[x]);
        return _ufs[x];
}
复制代码

  ^0 y+ _3 R2 f8 j+ g2 d) Z* l

合并
4 A* q: J7 }' R( }+ L4 ^% w7 G查找两个要合并元素的根节点根节点相同则不用合并如果两个根节点不同则将随便将其中一个集合的根节点连接到另一个集合根节点下。代码中的优化可要可不要对于效率影响不大。

具体实现
1 }4 b6 T$ n8 z: ]% z$ P* H, k

// 合并两个集合
0 W) d( F9 m% {: H
bool Union(int x, int y)
{
        int xroot = FindRoot(x);
9 _" i* q3 z8 i0 H) n8 j
        int yroot = FindRoot(y);
( q! ~+ a, i; Q2 Q1 E0 S4 E
        // xy为同一个集合的话合并失败
        if (xroot == yroot)
* G) z- T, O, T: Z
                return false;
        // 优化数据量小的结点并入数据量大的结点可要可不要
        // if (abs(_ufs[xroot])  
( X# k( i1 S. U# h/ g3 y) W5 `
[u][*][b]工程向实现参考代码[/b][/u] 
" e6 p0 r4 @! _- X" p% `6 D% d
[code]#include [i]
; j  D5 M2 |) O$ X* ^( D7 @1 `1 O
#include 
#include 
9 Q6 @* B4 {7 p
using namespace std;
0 R  e" l1 ]: d" f3 G7 q# W& {
class UnionFindSet
{
% u- L" B3 c2 X1 ~; P# w4 Z
public:
        // 默认全部都无父节点为-1
) a7 z- l2 L9 V8 Q4 Y% c0 \
        UnionFindSet(size_t sz)
                :_ufs(sz, -1)
$ e$ f' D; Y" R, V# ~6 o, {
        {}
3 z! T  P6 U# M! y! N% o" `* ~
        
: n1 B: l0 [# s$ }
        // 合并两个集合
        bool Union(int x, int y)
        {
4 O/ V) v& F( ^! N6 c
                int xroot = FindRoot(x);
                int yroot = FindRoot(y);
! u& P: d1 ]. t! o  l! G: q9 W
                // xy为同一个集合的话合并失败
7 G# _9 m# N2 s; w/ `, u
                if (xroot == yroot)
                        return false;
* r% e* ~% i' b' H! x
                // 优化数据量小的结点并入数据量大的结点
" f/ D5 u. T; q& ], z# Y
                if (abs(_ufs[xroot]) 
; M, k. \. f4 h6 c& K; T' l
                int root = x;
5 D8 a. O7 Q7 z! i4 t4 U' f; D: X
                // 查找到结点权值为负的根
                while (_ufs[root] >= 0)
                {
                        root = _ufs[root];
4 V: U+ u" i$ l6 `8 p& G: V
                }
' Q" q8 J/ Z+ a" ^. k; R8 V: h& p
                // 优化将被查找结点及以上的结点直接连接到根
* I5 }+ |- O, [- ^
                int cur = x;
                while (_ufs[cur] >= 0)
                {
                        int parent = _ufs[cur];
/ d4 }" Q7 @  A+ h: \! q
                        _ufs[cur] = root;
+ Y9 k; b- l3 b% K
                        cur = parent;
                }
                return root;
        }
5 P9 d# ^. z4 W9 l8 v1 q2 M
        // 获取有多少个集合
        int SetCount()
0 @3 G" q8 B' E; M1 m
        {
' w% s  [9 O3 v4 F0 R: N2 O* d0 H
                int cnt = 0;
. A: o- u* e+ Q8 ^6 }) S9 C1 N8 g
                for (int e : _ufs)
6 r% ^; N; e6 k* O8 x
                {
                        if (e 
9 ]% {, g$ b. U2 K, h
                return FindRoot(x) == FindRoot(y);
        }
private:
        vector[i] _ufs; // 根节点为负数其绝对值为集合中元素的个数孩子结点中存放父节点的序号
* y+ E- m+ X: \
};
% Y( R0 ?$ K9 N3 o$ R
复制代码

算法向实现
( {, a! Y' k0 o0 g4 h' }8 t

存储结构数组

初始化数组元素全部初始化为

-1
复制代码

。

存储数据根节点为负数其绝对值为集合中元素的个数孩子结点中存放父节点的下标。
4 w: |  ~! d* h5 l) I6 S实现思路与工程向实现基本相同只是算法向实现直接开好一个大数组作为并查集。
& U; z* I. x+ \- x& l* E

#include [i]
using namespace std;
& J* N( v  Y; M
const int N = 100010;
; c; `3 \: O  B9 V" @- ~
int p[N]; // 并查集
9 l8 [4 W* \1 D0 D9 h2 X: T
// 根结点查找 + 路径优化
0 U% D% X/ d/ K4 i1 U& i+ W* s% P2 Q
int find(int x)
{
9 c. a( B9 g5 D3 \2 t/ E
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void merge(int x, int y)
{
$ z7 g5 P0 D. Z
    p[find(x)] = find(y);
# @# ^! N& @. S9 i
}
, ]3 ~! l( A6 v
复制代码

" k/ ^: W. d) t% j" Z
相关例题
, X# A6 x% `& G5 {# ~9 ]4 {

4 o2 z: j: L/ I% ?, e 题目练习中的代码使用算法向的实现下面的例题都是并查集相关的应用希望大家可以将其掌握。
6 t! c6 v+ A4 m

合并集合
% t. I6 l, n# S# }1 f1 w$ I- R

d29a249abeb09dafdba2e60e0975b82f.png (154.57 KB, 下载次数: 0, 售价: 1 金钱)

2023-2-2 02:12 上传

点击文件名下载附件
d29a249abeb09dafdba2e60e0975b82f.png

8 I$ e" p' O, U  a

原题链接
复制代码

合并集合

算法思想
复制代码

2 e3 h5 x; E8 s6 |) Y: f/ \并查集基本实现 + 应用。
8 i' q9 e( o" c7 t! E
$ ]6 d7 m# ~1 O9 X, S  \

代码实现
复制代码

  a! _) g8 X! D( E5 b

并查集的元素初始化为自身下标方便理解。

// 模板并查集
#include [i]
+ j1 ], Y! ^6 @  K. r7 S
using namespace std;
const int N = 100010;
int p[N];
2 x) B, }$ x5 Z0 }
// 根结点查找 + 路径优化
; {  ~+ R# V+ K" o( T0 s7 ]
int find(int x)
{
; L0 Z) ~! A1 p6 |8 l4 j" z; U
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void merge(int x, int y)
. f6 L9 O. g: T$ S* o
{
    p[find(x)] = find(y);
}
int main()
  ]5 M; I7 ~9 ~
{
& t9 i; j/ D! e
    int n, m;
    scanf("%d%d", &n, &m);
+ Q8 C. X" L( ^; z/ {/ M4 r0 E
    for (int i = 1; i 
; A) s1 h1 ^5 `$ Y% i+ p. _
        char op[2];
        int x, y;
8 b% ~- {$ d9 W. T
        scanf("%s%d%d", op, &x, &y);
2 h7 P" P% X; Q( z' D
        if (op[0] == 'M') merge(x, y);
2 U7 s) }2 |  A( k0 Q6 C2 S6 }
        else
; ~* Q7 P: E2 ~# v. q7 w: Q& c# t
        {
            if (find(x) == find(y)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
% A2 f% ~$ r9 @- h( s$ |1 O
}
  r! e% N# ]  Z1 c; a7 P
复制代码

并查集的元素初始化为-1可以保存一个集合中的元素个数。
  i0 d& r) n$ t3 y

// 初始化为-1版本可以保存集合个数
#include [i]
#include 
#include 
' v) q& g, n+ K, V" X
using namespace std;
const int N = 100010;
. r) H7 c4 O' x* r+ m/ Q* ]
int p[N];
0 \1 _4 n, V& _- E! }6 M7 {; o
// 两种find函数的实现递归 和 迭代任取其一即可
// 根结点查找 + 路径优化
' v- t; |& J2 ^9 }
int find(int x)
( p7 a) w2 E/ f+ k( `. M/ R+ f
{
/ t+ S4 V. N5 t$ u
    if (p[x] >= 0) p[x] = find(p[x]);
5 ^. t# V; Q5 Q! t0 R4 z
    else return x;
# g9 u& v' V7 d3 p
}
// 根结点查找 + 路径优化
! S; ]- @$ W  \/ p6 ]- m
int find(int x)
{
    int cur = x;
    vector[i] v;
    // 循环结束时cur为根结点坐标
    while (p[cur] >= 0)
    {
. l3 l4 z" w5 D$ }/ D" P4 n, p" @1 ?
        v.push_back(cur);
1 v7 G: Y* d# j) w- Y6 p: I
        cur = p[cur];
% L* _, S5 M$ N
    }
    // 将路径上的结点全部直接连接到cur节点上
& [! o* W1 Y4 _6 O9 o
    for (auto e : v) p[e] = cur;
    return cur;
}
  W: i6 C9 B* z9 \0 Y4 H
void merge(int x, int y)
{
    if (find(x) != find(y))
    {
: m0 o* v$ D" N* z
        p[find(y)] += p[find(x)];
        p[find(x)] = find(y);
    }
, f: I7 N- g8 U. {
}
int main()
* \7 S  Y& X6 T+ G; V2 E8 N
{
    int n, m;
: d" w% I) ?' [% O+ O- p, t. P( E, {
    scanf("%d%d", &n, &m);
    memset(p, -1, 4 * N);
    while (m--)
8 C' H7 {' i) p; y# L
    {
6 p0 B: ]/ A; _: z( Y( i1 K4 h
        char op[2];
        int x, y;
        scanf("%s%d%d", op, &x, &y);
- C. y' t0 J# \! y
        if (op[0] == 'M') merge(x, y);
- l, W, [6 m  Z: r
        else
, J5 Q; O. u4 i* C3 v
        {
            if (find(x) == find(y)) puts("Yes");
+ P* ~3 x$ |/ ?; p
            else puts("No");
        }
    }
+ ]3 U7 A% A# |; x+ i3 e( m& ?6 H
    return 0;
$ }6 A( A9 Q, e  u
}
$ ?1 V$ x8 E, p$ D+ x9 ^
复制代码

& F: B: Y9 l1 }8 f8 X4 Y/ f连通块中点的数量
% V3 z5 m' s5 V% ~

1c1c8e4c2530f45af42323f6c3937d7e.png (180.4 KB, 下载次数: 0, 售价: 3 金钱)

2023-2-2 02:12 上传

点击文件名下载附件
1c1c8e4c2530f45af42323f6c3937d7e.png

, c6 Y/ O3 i4 b; {$ t) A- Q

原题链接
复制代码

连通块中点的数量

7 W) D2 K" w. V4 r# T

算法思想
复制代码

基本的并查集应用下面给出两种实现方式

并查集的元素初始化为-1此时根节点的绝对值就为此集合的元素个数。

并查集的元素初始化为自身下标额外维护一个数组存储集合中元素个数。

代码实现
复制代码

并查集的元素初始化为-1可以保存一个集合中的元素个数。
# H1 a( [8 L. M! C

// 初始化为-1版本
#include [i]
5 I* W7 j8 o. P  b+ f& \( `
#include 
using namespace std;
const int N = 100010;
int p[N];
// 根结点查找 + 路径优化
int find(int x)
{
    if (p[x] >= 0) p[x] = find(p[x]);
    else return x;
% x, a+ d: A# e) U- U
}
void merge(int x, int y)
{
1 H6 C" K3 t5 ~. d- t/ u8 s
    if (find(x) != find(y))
    {
6 h4 \  h1 G& W. ~9 [
        p[find(y)] += p[find(x)];
        p[find(x)] = find(y);
) ]& [$ }) M$ k
    }
}
1 P# ]4 t9 H) @# E" l
int size(int x)
7 Y% L) ?' @1 {6 I/ g
{
    return abs(p[find(x)]);
}
4 Q1 a$ O7 \& `; ?4 m
int main()
{
6 M/ @% v* r' a  u- i$ W% P
    int n, m;
) B7 ^4 q) S7 |+ \2 G' Z8 F
    scanf("%d%d", &n, &m);
    memset(p, -1, 4 * N);
    while (m--)
6 w9 _) E, I1 e* b( n' n5 m
    {
        char op[3];
9 L* a) s" b" ^& g! G0 _0 j
        int x, y;
        scanf("%s", op);
9 y7 Z9 L9 f$ ~3 Q( [
        if (op[0] == 'C')
+ h! G& }* d4 p) `3 S* R
        {
/ Q( Z: |# T' V7 V, F4 p
            scanf("%d%d", &x, &y);
            merge(x, y);
        }
        else if (op[1] == '1')
6 M- F3 l& n+ w- ^7 f9 W9 j4 x6 Y
        {
            scanf("%d%d", &x, &y);
            if (find(x) == find(y)) puts("Yes");
1 \, j, A: \6 C# Z6 [
            else puts("No");
        }
" V" d; z. s2 _/ V
        else
! w9 M, ]& r9 p1 r9 q8 I
        {
- n6 _+ S; i: O1 @1 E6 m
            scanf("%d", &x);
. y& M( m$ Z  y- E8 q* z7 \" x7 ^
            printf("%d\n", size(x));
        }
: Y1 Z4 {- \) m% v9 A
    }
9 n3 N! E1 \( b+ ^6 L
    return 0;
/ P) x6 J" W" a' [, D3 ~# H& R6 G$ K
}
复制代码

2 w8 O3 i9 V$ N- M* e

并查集的元素初始化为自身下标维护一个存储结点个数的数组。

#include [i]
( f, k$ a/ @1 D7 K3 O2 T
using namespace std;
( d" j$ b2 l) N6 j6 {+ m9 p( Y/ a
const int N = 100010;
int p[N], s[N]; // p为父节点数组s为集合大小数组
1 i$ f, S& |$ F1 L+ g3 |1 M. z
// 根结点查找 + 路径优化
2 \" C$ ^3 p2 }- ]" I+ ~
int find(int x)
- {7 Q/ P) }/ ]/ d7 v+ G5 ^
{
0 I3 W; N; `! x6 f! E1 k+ h
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
6 J1 u: h' K$ J
void merge(int x, int y)
: `0 q3 O4 Q! G) m
{
    // 合并时要先判断是否是同一个集合的
    if (find(x) != find(y))
    {
; `/ R3 J+ |" W% a6 m1 |$ U3 p8 T" m. G
        // 头节点的数量才有效
        s[find(y)] += s[find(x)];
        p[find(x)] = find(y);
    }
. V# A1 \6 b7 Q) t
}
5 N" G* q, k" y# }3 }
int main()
% \& ?  t/ Z3 g- ?5 [( t2 t& N0 s5 A
{
  D' U' k* J* Y. W6 M: I
    int n, m;
$ ^8 F. r4 B0 o! n
    scanf("%d%d", &n, &m);
; h. q! z" p5 y4 d* o4 Q1 z2 n- A
    for (int i = 1; i 
        char op[3];
        int x, y;
/ J2 C% ]  i. B6 s( u! d, a2 L! C% l
        scanf("%s", op);
2 [$ e' X, T) @6 K1 Z7 c6 c9 b
        if (op[0] == 'C')
        {
            scanf("%d%d", &x, &y);
            merge(x, y);
5 M6 D6 \% O' ^* T" O0 H
        }
        else if (op[1] == '1')
3 Y) P! u( P" |# O
        {
            scanf("%d%d", &x, &y);
  C( d) m% T  `
            if (find(x) == find(y)) puts("Yes");
8 @4 x' Z5 e8 i9 \) _* O0 S
            else puts("No");
9 ?- j4 J: e" ~8 k
        }
6 |9 t) {6 t/ t+ u2 _1 i
        else
, y# y5 a) I+ g4 g( C6 O$ i
        {
2 Z9 i2 t  f# k7 A8 P# p- l  b
            scanf("%d", &x);
; P; P' T/ X* I7 X8 I
            printf("%d\n", s[find(x)]);
        }
5 I$ Y, d4 D3 S  |1 B' D: ~1 m
    }
+ e$ @0 F% N# F$ U- p
    return 0;
- q$ D# j! M" _* I, p. h/ l! S
}
5 n* T) _2 P; {. C
复制代码

?食物链
9 e9 F. H) D# w9 \

6e760199d53597a3080e2340a9cfbd09.png (273.25 KB, 下载次数: 0, 售价: 3 金钱)

2023-2-2 02:12 上传

点击文件名下载附件
6e760199d53597a3080e2340a9cfbd09.png

: g1 V1 _" h1 u  F

原题链接
复制代码

食物链

1 z9 b" h5 E: W; _" O. t  [

算法思想
复制代码

! }+ W; l5 s& d3 w
9 Z8 g% n( }5 b  r并查集的元素初始化为自身下标额外维护一个距离根节点路径长度的数组。规定

x
复制代码

和

 y
复制代码

为同类

x
复制代码

到根节点的距离 和

y
复制代码

到根节点的距离同余

3
复制代码

x
复制代码

到根节点的距离和

y
复制代码

到根节点的距离模

3
复制代码

都为0。

x
复制代码

吃

 y
复制代码

x
复制代码

到根节点的距离mod

3
复制代码

-

y
复制代码

到根节点的距离mod

3
复制代码

= 1。

代码实现
复制代码

#include [i]
6 i& q! P4 w  A
using namespace std;
2 p" b& C+ L' y: ~5 E' R3 H
const int N = 50010;
6 G! ?6 A  l  _5 I2 y3 n: B
int p[N], d[N]; // p为堆d为每个结点到根节点的距离d可以为负
$ I2 {7 b* o& J3 L2 N
int find(int x)
, Q, I" L4 m& F7 a5 G) ]( Z
{
    if (p[x] != x)
0 [1 B2 u0 K8 y* o; L9 i- d5 T& E# i
    {
        int root = find(p[x]); // 先找到根节点并且将从根节点到父节点的距离全部更新
0 s# X% A' L6 ^
        d[x] += d[p[x]];// 现在到根的距离 等于 自己原本到父节点的距离 + 父节点到根的距离已在上面递归中更新
        p[x] = root;
: e  D8 y, `- Z' U
    }
' {, `5 {% r" E) n3 K& Z8 E: b
    return p[x];
}
1 n4 M. g0 I( }* Q
int main()
; m) Q( v" n3 S
{
; f9 }  z5 T+ f  D  [4 F
    int n, m;
    scanf("%d%d", &n, &m);
2 L0 _; p1 b4 l5 V! o5 j
    for (int i = 1; i 
! w! E5 a; S  y4 M5 n
        int op, x, y;
" _8 G6 _, ]: O& r8 v: |/ X
        scanf("%d%d%d", &op, &x, &y);
% F7 X( U# ^3 C4 {; X* y
        if (x > n || y > n) ans++;
* e+ E9 |' w2 N5 C0 a( R3 K  S
        else
# s( T% A; S0 m& t
        {
            int rx = find(x), ry = find(y);
            if (op == 1)
; b2 `5 _$ R6 b# d, L! q2 r6 n0 N
            {
                // 当是同一个集合 并且 不是一个种类时
                if (rx == ry && (d[x] - d[y]) % 3 != 0) ans++;
                else if (rx != ry) // 不是一个集合将其合并
  L  ]( a3 W5 m* @) p8 T9 g
                {
+ q7 e; H1 A0 _, Q: o
                    d[rx] = d[y] - d[x]; // rx并入ry后(d[rx] + d[x] - d[y]) % 3 = 0取特殊解d[rx] + d[x] - d[y] = 0
                    p[rx] = ry;
                }
; }$ W6 S0 o+ |; ^" |+ v
                // 还有一种情况就是同一个集合同一个种类这个情况不用管所以就不讨论了
            }
/ P) V- q  E/ _" x2 I
            else
            {
. g# O! U8 }+ M' N3 G
                // x 吃 y则 (d[x] - d[y] - 1) % 3 = 0
                if (rx == ry && (d[x] - d[y] - 1) % 3 != 0) ans++;
                else if (rx != ry) // 不是一个集合建立关系
5 a. |( r" v5 M  P8 o1 J/ @
                {
  \# F( _8 r4 R" _
                    d[rx] = d[y] - d[x] + 1; // rx并入ry后(d[rx] + d[x] - d[y] - 1) % 3 = 0取特殊解d[rx] + d[x] - d[y] - 1 = 0
& K/ s7 t& O2 b- h5 p2 f0 G
                    p[rx] = ry;
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
0 A. c8 b9 y4 k4 Z6 i( v
}
复制代码

: z1 l& B4 m1 y1 V1 o; ^, Q) k后记

( A- w8 Y% G  f$ W( |! B未来在图相关的算法中我们还会使用使用并查集希望大家可以尽快掌握一起加油吧

% r+ r2 v9 X- F0 l如果解析有不对之处还请指正我会尽快修改多谢大家的包容。

" q$ X" l$ O+ E6 z$ t如果大家喜欢这个系列还请大家多多支持啦

如果这篇文章有帮到你还请给我一个

大拇指
复制代码

和

小星星
复制代码

??支持一下白晨吧喜欢白晨【算法】或【数据结构】系列的话不如

关注
复制代码

白晨以便看到最新更新哟

: b9 O# R; K- Q我是不太能熬夜的白晨我们下篇文章见。
& ^0 K3 B" n9 I: h
9 H) w6 r3 x8 s8 l4 f               
/ _  J- W3 }" \               
               
本文来源csdn，由Java吧转载发布，观点不代表Java吧的立场，转载请标明来源出处：https://www.java8.com