【数据结构】并查集

た入场券 2022-11-09 12:52 170阅读 0赞

### 并查集 ###

*  需求引出并查集
 *  并查集（Union Find）
 *  如何存储数据？
 *  接口定义
 *  元素的初始化
 *  UnionFind.java（abstract）
 *   *  Quick Find
     *   *  Union 实现
         *  find 实现
         *  Quick Find 完整代码
     *  Quick Union
     *   *  Union 实现
         *  find 实现
         *  Quick Union 完整实现
     *  Quick Union – 优化
 *  优化 Union()
 *   *  Quick Union – 基于size的优化
     *  Quick Union – 基于rank的优化
 *  优化 Find()
 *   *  路径压缩（Path Compression）
     *  路径分裂（Path Splitting）
     *  路径减半（Path Halving）
 *  总结
 *  自定义类型使用并查集
 *   *  自定义类型并查集代码

# 需求引出并查集 #

假设有 n 个村庄，有些村庄之间有连接的路，有些村庄之间并没有连接的路  
![在这里插入图片描述][20210315141642712.png]  
设计一个数据结构，能够快速执行 2 个操作：

*  查询 2 个村庄之间是否有连接的路
 *  连接 2 个村庄

如果使用数组、链表、平衡二叉树、集合(Set) 都可以完成需求，但是查询、连接的时间复杂度都是  O ( n ) O(n) O(n)。

并查集能做到查询、连接的均摊时间复杂度都是  O ( α ( n ) ) O(α(n)) O(α(n))， α ( n ) α(n) α(n) < 5，非常适合解决这类“连接”相关的问题。

# 并查集（Union Find） #

并查集也叫作不相交集合（Disjoint Set）

并查集有 2 个核心操作:

*  查找（Find）：查找元素所在的集合  
    (这里的集合并不是特指 `Set` 这种数据结构，是指广义的数据集合)
 *  合并（Union）：将两个元素所在的集合合并为一个集合

有 2 种常见的实现思路：

Quick Find

*  查找（Find）的时间复杂度：O(1)
 *  合并（Union）的时间复杂度：O(n)

Quick Union

*  查找（Find）的时间复杂度： O ( l o g n ) O(logn) O(logn)，可以优化至  O ( α ( n ) ) O(α(n)) O(α(n))，  α ( n ) α(n) α(n) < 5
 *  合并（Union）的时间复杂度： O ( l o g n ) O(logn) O(logn)，可以优化至  O ( α ( n ) ) O(α(n)) O(α(n))， α ( n ) α(n) α(n) < 5

# 如何存储数据？ #

假设并查集处理的数据都是整型，那么可以用整型数组来存储数据。

*  数组索引代表元素值
 *  索引对应的值代表这个元素的根节点

将｛0，1，2，3，4，5，6，7｝存储到数组中，如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]  
因此，并查集是可以用数组实现的树形结构（二叉堆、优先级队列也是可以用数组实现的树形结构）

# 接口定义 #

/**
     * 查找v所属的集合（根节点）
     */
    public abstract int find(int v);
    
    /**
     * 合并v1、v2所在的集合
     */
    public abstract void union(int v1, int v2);
    
    /**
     * 检查v1、v2是否属于同一个集合
     */
    public boolean isSame(int v1, int v2);

# 元素的初始化 #

初始化，每个元素各自属于一个单元素集合  
![在这里插入图片描述][20210315145437730.png]

private int[] parents;
    public UnionFind(int capacity){
        
    	if(capacity < 0){
        
    		throw new IllegalArgumentException("capacity must >= 1");
    	}
    	parents = new int[capacity];
    	for (int i = 0; i < parents.length; i++) {
        
    		parents[i] = i;
    	}
    }

# UnionFind.java（abstract） #

这是并查集的抽象类，后面的所有并查集都将继承它

public abstract class UnionFind {
        
    	protected int[] parents;
    	
    	public UnionFind(int capacity) {
        
    		if(capacity < 0){
        
    			throw new IllegalArgumentException("capacity must be >= 1");
    		}
    		parents = new int[capacity];
    		for (int i = 0; i < parents.length; i++) {
        
    			parents[i] = i;
    		}
    	}
    	/**
    	 * 查找v所属的集合(根结点)
    	 */
    	public abstract int find(int v);
    	/**
    	 * 合并v1、v2所在的集合
    	 */
    	public abstract void union(int v1, int v2);
    	/**
    	 * 检查v1、v2是否属于同一集合
    	 */
    	public boolean isSame(int v1, int v2){
        
    		return find(v1) == find(v2);
    	}
    	/**
    	 * 检查传入值的合法性
    	 */
    	protected void rangeCheck(int v) {
        
    		if(v < 0 || v >= parents.length){
        
    			throw new IllegalArgumentException("v is out of bounds");
    		}
    	}
    
    }

## Quick Find ##

### Union 实现 ###

Quick Find 的 `union(v1, v2)`：让 v1 所在集合的所有元素 都指向 v2 的根节点

1.  将｛0，1，2，3，4，5｝初始化为并查集，每个元素各自属于一个单元素集合：\{0\}, \{1\}, \{2\}, \{3\}, \{4\} ；  
    初始化后的，集合根节点就是 单元素本身  
    ![在这里插入图片描述][20210315150919548.png]
2.  合并 1 和 0，`union(1, 0)`，即 \{1\} 集合的所有元素，都指向了 \{2\} 的根节点。  
    ![在这里插入图片描述][20210315151347420.png]
3.  然后，合并 1 和 2，`union(1, 2)`，1 所在集合 \{0, 1\} 所有元素，都指向集合 \{2\} 的根节点。  
    ![在这里插入图片描述][20210315151543412.png]
4.  再合并 3 和 4，`union(3, 4)`，即 \{3\} 集合的所有元素，都指向了 \{4\} 的根节点  
    ![在这里插入图片描述][20210315151733300.png]
5.  合并 0 和 3，`union(0, 3)`，0 所在集合为 \{0, 1, 2\}，3 所在集合为 \{3,4\} 。  
    将和 0 相同的根节点的元素，全部改为 3 的根节点；  
    相当于将前面集合的元素压平，指向后面集合元素的根节点  
    ![在这里插入图片描述][20210315153605617.png]

union 时间复杂度： O ( n ) O(n) O(n)

/**
     * 将v1所在集合的所有元素都嫁接到v2的父节点上
     *  v1    v2   union(v1,v2)
     *  0     4	       4
     * 1 2    3     0 1 2 3
     */
    public void union(int v1, int v2) {
        
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;
        // 循环遍历数组，发现有值等于p1，就将该值改成p2
        for (int i = 0; i < parents.length; i++) {
        
            if (parents[i] == p1) {
        
                parents[i] = p2;
            }
        }
    }

### find 实现 ###

Quick Find 查找的时候，由于数组中存储的就是根节点，因此直接取出即可

Quick Find 的高度永远保持 <= 2  
![在这里插入图片描述][20210315154234496.png]  
find 时间复杂度： O ( 1 ) O(1) O(1)

/**
     * 父节点就是根节点
     */
    public int find(int v){
        
    	rangeCheck(v);
    	return parents[v];
    }

### Quick Find 完整代码 ###

/**
     * Quick Find
     */
    public class UnionFind_QF extends UnionFind {
        
    
        public UnionFind_QF(int capacity) {
        
            super(capacity);
        }
    
        @Override
        public int find(int v) {
        
            super.rangeCheck(v);
            // quick find只有2层，所以数组里面的值就是该索引的根节点（父节点）
            return parents[v];
        }
    
        @Override
        public void union(int v1, int v2) {
        
            int p1 = find(v1);
            int p2 = find(v2);
            if (p1 == p2) return;
            // 循环遍历数组，发现有值等于p1，就将该值改成p2
            for (int i = 0; i < parents.length; i++) {
        
                if (parents[i] == p1) {
        
                    parents[i] = p2;
                }
            }
    
        }
    }

## Quick Union ##

### Union 实现 ###

Quick Union 的 `union(v1, v2)`：让 v1 的根节点 指向 v2 的根节点

1.  将｛0，1，2，3，4，5｝初始化为并查集，每个元素各自属于一个单元素集合  
    ![在这里插入图片描述][20210315155202326.png]
2.  `union(1, 0)`，1的根结点(还是1) 指向 0的根结点(还是0)  
    ![在这里插入图片描述][20210315155246376.png]
3.  `union(1, 2)`，1的根结点(0) 指向 2的根结点(2)  
    ![在这里插入图片描述][2021031515532180.png]
4.  `union(3, 4)`，3的根结点(3) 指向 4的根结点(4)  
    ![在这里插入图片描述][2021031515544779.png]
5.  `union(3, 1)`，3的根结点(4) 指向 1的根结点(2)  
    先找根节点，3的根节点是4；1的根节点是2，所以将3的根节点变成2即可  
    ![在这里插入图片描述][20210315155511364.png]

时间复杂度：O(logn)

/**
     * 将v1的根节点 嫁接到 v2的根节点上
     */
    public void union(int v1, int v2) {
        
    	int p1 = find(v1);
    	int p2 = find(v2);
    	if (p1 == p2) return;
    	parents[p1] = p2;
    }

### find 实现 ###

Quick Union 的查找，需要通过父节点不断往上找，直到找到根节点

/**
     * 通过parent链条不断往上找，直到找到根节点
     */
     public int find(int v) {
        
    	rangeCheck(v);
    	while(v != parents[v]){
        
    		v = parents[v];
    	}
    	return v;
    }

### Quick Union 完整实现 ###

/**
     * Quick Union
     */
    public class UnionFind_QU extends UnionFind {
        
    
    	public UnionFind_QU(int capacity) {
        
    		super(capacity);
    	}
    	/**
    	 * 通过parent链条不断往上找，直到找到根节点
    	 */
    	@Override 
    	public int find(int v) {
        
    		rangeCheck(v);
    		while(v != parents[v]){
        
    			v = parents[v];
    		}
    		return v;
    	}
    	/**
    	 * 将v1的根节点嫁接到v2的根节点上
    	 */
    	public void union(int v1, int v2) {
        
    		int p1 = find(v1);
    		int p2 = find(v2);
    		if(p1 == p2) return;
    		parents[p1] = p2;
    	}
    
    }

## Quick Union – 优化 ##

一般用的更多的是 Quick Union，我们研究一下它的优化方案

在 union 的过程中，可能会出现树不平衡的情况，甚至退化成链表  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]  
有 2 种常见的优化方案：

*  基于 `size` 的优化：元素少的树 嫁接到 元素多的树
 *  基于 `rank` 的优化：矮的树 嫁接到 高的树

# 优化 Union() #

## Quick Union – 基于size的优化 ##

不是固定的让某一棵树嫁接到另一棵树，让元素少的树 嫁接到 元素多的树  
![在这里插入图片描述][20210315163116349.png]  
该类继承了 `UnionFind_QU`，表明它是在 Quick Union 的基础上优化，并且只需要重写`uniont(int v1, int v2)`即可，`find(int v)`无需做任何变化

public class UnionFind_QU_Size extends UnionFind_QU {
        
    	private int[] sizes;
    
    	public UnionFind_QU_Size(int capacity) {
        
    		super(capacity);
    
    		// 最开始每个元素都是一个集合，初始化一个sizes数组，
    		// 数组 sizes[根节点] = 元素数量
    		sizes = new int[capacity];
    		for (int i = 0; i < sizes.length; i++) {
        
    			sizes[i] = 1; // 以i为根节点的树的元素个数
    		}
    	}
    
    	/**
    	 * 将v1的根节点嫁接到v2的根节点上
    	 */
    	public void union(int v1, int v2) {
        
    		int p1 = find(v1);
    		int p2 = find(v2);
    		if (p1 == p2) return;
    
    		// 将元素少的树 嫁接到 元素多的树上
    		if (sizes[p1] < sizes[p2]) {
        
    			parents[p1] = p2; // 将p1嫁接到p2上
    			sizes[p2] += sizes[p1]; // 将p1集合的元素，添加到p2集合里
    		} else {
        
    			parents[p2] = p1;
    			sizes[p1] += sizes[p2];
    		}
    	}
    
    }

## Quick Union – 基于rank的优化 ##

上面所说的，基于size的优化，也可能会存在树不平衡的问题  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]  
基于rank的优化，让矮的树 嫁接到 高的树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]  
该类继承了 UnionFind\_QU，表明它是在 Quick Union 的基础上优化，并且只需要重写`uniont(int v1, int v2)`即可，`find(int v)`无需做任何变化

public class UnionFind_QU_Rank extends UnionFind_QU {
        
    	private int[] ranks;
    
    	public UnionFind_QU_Rank(int capacity) {
        
    		super(capacity);
    
    		// 最开始每个元素都是一个集合，初始化一个ranks数组，
    		// 数组 ranks[根节点] = 树的高度
    		ranks = new int[capacity];
    		for (int i = 0; i < ranks.length; i++) {
        
    			ranks[i] = 1; // 以i为根节点的树的高度
    		}
    	}
    	
    	public void union(int v1, int v2) {
        
    		int p1 = find(v1);
    		int p2 = find(v2);
    		if (p1 == p2) return;
    
    		// 将矮的树 嫁接到 高的树；
    		// 嫁接后，整体树高没有发生改变，还是以高的为准
    		if (ranks[p1] < ranks[p2]) {
        
    			parents[p1] = p2;
    		} else if (ranks[p1] > ranks[p2]) {
        
    			parents[p2] = p1;
    		} else {
         // 两个树的高度一样，嫁接后高度会+1
    			parents[p1] = p2; // 将p1嫁接到p2上
    			ranks[p2] += 1; // p2的高度会+1
    		}
    	}
    }

# 优化 Find() #

## 路径压缩（Path Compression） ##

虽然有了基于 rank 的优化，树会相对平衡一点，但是随着 union 次数的增多：树的高度依然会越来越高，导致 find 操作变慢，尤其是底层节点 (因为 find 是不断向上找到根节点)

什么是路径压缩？

*  在 find 时使路径上的所有节点都指向根节点，从而降低树的高度。

如下图，

*  `find(1)` 使路径上的 1，2 都指向了根结点 4
 *  `find(0)` 使路径上的 0 指向了根结点 4
 *  `find(7)` 使路径上的 7 指向了根结点 4

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 4]  
该类继承了 UnionFind\_QU\_Rank，表明它是在 Quick Union 的 rank 优化的基础上，再优化，并且只需要重写`find(int v)`即可

/**
     * Quick Union - 基于rank的优化 - 路径压缩(Path Compression)
     * @author JL Qin
     *
     */
    public class UnionFind_QU_Rank_PC extends UnionFind_QU_Rank {
        
    
    	public UnionFind_QU_Rank_PC(int capacity) {
        
    		super(capacity);
    	}
    	
    	@Override
    	public int find(int v) {
         // v == 1, parents[v] == 2
    		rangeCheck(v);
    		if (parents[v] != v) {
        
    			// 递归将v的父节点 指向 根节点
    			parents[v] = find(parents[v]);
    		}
    		// 返回v的父节点，也就是根节点
    		return parents[v];
    	}
    }

路径压缩：使路径上的所有节点都指向根节点，所以实现成本稍高。

还有 2 种更优的做法，不但能降低树高，实现成本也比路径压缩低：

*  路径分裂（Path Spliting）
 *  路径减半（Path Halving）

路径分裂、路径减半的效率差不多，但都比路径压缩要好。

## 路径分裂（Path Splitting） ##

路径分裂：使路径上的`每个节点`都指向其祖父节点（parent的parent）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]  
该类继承了 UnionFind\_QU\_R，表明它是在 Quick Union 的 rank 优化的基础上，再优化，并且只需要重写`find(int v)`即可

/**
     * Quick Union - 基于rank的优化 - 路径分裂(Path Splitting)
     * @author JL Qin
     *
     */
    public class UnionFind_QU_Rank_PS extends UnionFind_QU_Rank {
        
    
    	public UnionFind_QU_Rank_PS(int capacity) {
        
    		super(capacity);
    	}
    	
    	@Override
    	public int find(int v) {
         
    		rangeCheck(v);
    		while (v != parents[v]) {
        
    			int p = parents[v];
    			parents[v] = parents[parents[v]];
    			v = p;
    		}
    		return v;
    	}
    }

## 路径减半（Path Halving） ##

路径减半：使路径上`每隔一个节点`就指向其祖父节点（parent的parent）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]  
该类继承了 UnionFind\_QU\_Rank，表明它是在 Quick Union 的 rank 优化的基础上，再优化，并且只需要重写`find(int v)`即可

/**
     * Quick Union - 基于rank的优化 - 路径减半(Path Halving)
     * @author JL Qin
     *
     */
    public class UnionFind_QU_Rank_PH extends UnionFind_QU_Rank {
        
    
    	public UnionFind_QU_Rank_PH(int capacity) {
        
    		super(capacity);
    	}
    
    	// 路径减半：使路径上每隔一个节点就指向其祖父节点（parent的parent）
    	@Override
    	public int find(int v) {
         
    		rangeCheck(v);
    		while (v != parents[v]) {
        
    			// 将v的父节点 指向 v的祖父节点；
    			// 就是将v的父节点，变成了祖父节点
    			parents[v] = parents[parents[v]];
    			// 经过上面那句代码，刚好 v的parent 就是 parent的parent；
    			// 然后parent的parent也重复 v 的操作,
    			// 所以将 v 指向 parents[v]即可
    			v = parents[v];
    		}
    		return v;
    	}
    }

# 总结 #

摘自《维基百科》  
![在这里插入图片描述][20210317090856397.png]  
大致意思：

使用路径压缩、分裂 或 减半 \+ 基于rank 或 size的优化 可以确保每个操作的均摊时间复杂度为  O ( α ( n ) ) O(α(n)) O(α(n)) ， α ( n ) α(n) α(n) < 5。

建议搭配：

*  Quick Union
 *  基于 rank 的优化
 *  Path Halving 或 Path Spilitting

# 自定义类型使用并查集 #

方案一：通过一些方法将自定义类型转为整型后使用并查集（比如生成哈希值）

方案二：使用链表+映射（Map）

## 自定义类型并查集代码 ##

import java.util.HashMap;
    import java.util.Map;
    import java.util.Objects;
    
    public class GenericUnionFind<V> {
        
    	private Map<V, Node<V>> nodes = new HashMap<>();
    
    	// 初始化集合
    	// 使用并查集前，需要为对象创建集合
    	public void makeSet(V v) {
        
    		if (nodes.containsKey(v)) return;
    
    		nodes.put(v, new Node<>(v));
    	}
    	
    	/**
    	 * 找出v的根节点
    	 */
    	private Node<V> findNode(V v) {
        
    		Node<V> node = nodes.get(v);
    		if (node == null) return null;
    
    		while (!Objects.equals(node.value, node.parent.value)) {
        
    			node.parent = node.parent.parent;
    			node = node.parent;
    		}
    		return node;
    	}
    	
    	public V find(V v) {
        
    		Node<V> node = findNode(v);
    		return node == null ? null : node.value;
    	}
    	
    	public void union(V v1, V v2) {
        
    		Node<V> p1 = findNode(v1);
    		Node<V> p2 = findNode(v2);
    		if (p1 == null || p2 == null) return;
    		if (Objects.equals(p1.value, p2.value)) return;
    		
    		if (p1.rank < p2.rank) {
        
    			p1.parent = p2;
    		} else if (p1.rank > p2.rank) {
        
    			p2.parent = p1;
    		} else {
        
    			p1.parent = p2;
    			p2.rank += 1;
    		}
    	}
    	
    	public boolean isSame(V v1, V v2) {
        
    		return Objects.equals(find(v1), find(v2));
    	}
    	
    	private static class Node<V> {
        
    		V value;
    		Node<V> parent = this; // 父节点指向自己
    		int rank = 1; // 树高为1
    		Node(V value) {
        
    			this.value = value;
    		}
    	}
    }

[20210315141642712.png]: /images/20221023/673fe2e070a34ec5b6f8c31f1cb2b64a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221023/a254b32e7a7140778249e23493e5b12f.png
[20210315145437730.png]: /images/20221023/76fd5777f2dd4c63adc1e856ddc104ab.png
[20210315150919548.png]: /images/20221023/aa8fea15678e42c4a5599712599cc6e3.png
[20210315151347420.png]: /images/20221023/adedb266026e4b988d481f94e16e7459.png
[20210315151543412.png]: /images/20221023/0260f17309a8401f8b29085024ff330f.png
[20210315151733300.png]: /images/20221023/159ae461ea45465e921db9c54146bb69.png
[20210315153605617.png]: /images/20221023/02d80fdd7c95429c829f1fe98bb67ecc.png
[20210315154234496.png]: /images/20221023/2a5d60472d12473c9c4482152ed5139c.png
[20210315155202326.png]: /images/20221023/d6f7570d62ac461684e531f12d9e96ae.png
[20210315155246376.png]: /images/20221023/246d8a6ad1e54ea9843ad6a30c2f3bb1.png
[2021031515532180.png]: /images/20221023/d3375c09c5664873a785e503bd4203e1.png
[2021031515544779.png]: /images/20221023/d7a4283d1f2044b48d2d3df3bb48caac.png
[20210315155511364.png]: /images/20221023/9789618a6bd246fc9a9b69c98ec17b3d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]: /images/20221023/382f3ef469b44f138f0a1923058ad40c.png
[20210315163116349.png]: /images/20221023/f8f73aa508ac44629aa12ef02abf411f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]: /images/20221023/3c1d67662b014b23ae7bff79b0661e60.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]: /images/20221023/74340299299242c98be66142380fabcb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 4]: /images/20221023/153aa24f504749aca45b6bf917db1cb2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]: /images/20221023/fa0000b7c75846ddbbafdd799eb0f059.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]: /images/20221023/faf6febf332546458a5fe379c7b4fe64.png
[20210317090856397.png]: /images/20221023/f0d7e9ab5f8f4e15b895008d5f644574.png