C++并查集的原理與使用方法

更新時(shí)間：2025年12月21日 14:52:53 作者：落羽的落羽

并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu),用于處理不相交集合的合并及查詢問題,下面這篇文章主要介紹了C++并查集原理與使用方法的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下

一、并查集的概念

在一些場(chǎng)景中，需要將n個(gè)不同元素劃分為一些不相交的集合。開始時(shí)，每個(gè)元素各成一個(gè)元素，然后按一定的規(guī)律將屬于同一組的元素合并。這個(gè)過程中需要反復(fù)用到查詢一個(gè)元素是否屬于某個(gè)集合的算法。適合用于這種場(chǎng)景的數(shù)據(jù)結(jié)構(gòu)是并查集（Union-Find Set）！

并查集的底層結(jié)構(gòu)本質(zhì)上是一片森林（多棵樹的集合）

比如，我現(xiàn)在有九個(gè)數(shù)據(jù)元素，給他們編號(hào)0~8：

按照某種需求，這些數(shù)據(jù)被分組合并為：

按照其他需求，這些樹可以繼續(xù)合并下去…

而這個(gè)森林，可以用一個(gè)數(shù)組記錄下來元素的關(guān)系！
我們可以規(guī)定并查集用數(shù)組下標(biāo)代表每個(gè)元素，數(shù)組內(nèi)容代表元素之間的關(guān)系：

數(shù)組下標(biāo)代表元素編號(hào)
如果數(shù)組內(nèi)容為負(fù)整數(shù)，代表這個(gè)下標(biāo)是根，絕對(duì)值表示它這棵樹的元素個(gè)數(shù)
如果數(shù)組內(nèi)容為非負(fù)整數(shù)，代表這個(gè)下標(biāo)不是根，數(shù)組內(nèi)容是它的父親在數(shù)組中的下標(biāo)

比如，上面的森林例子，用并查集數(shù)組表示，就是：

如果元素的數(shù)據(jù)類型不能直接作為數(shù)組下標(biāo)，只要在實(shí)現(xiàn)中用std::map之類的結(jié)構(gòu)，建立元素到下標(biāo)的映射關(guān)系，就能解決了！

通過并查集的特點(diǎn)，可以看出并查集一般能解決：

查找元素屬于哪個(gè)集合：沿著數(shù)組一直找到元素為負(fù)數(shù)，就是根
查看兩個(gè)元素是否屬于一個(gè)集合：看看這兩個(gè)元素的根是否相同
將兩個(gè)集合歸并為一個(gè)集合：假如要將下標(biāo)a的樹合并到下標(biāo)b的樹中，arr[b] += arr[a]，arr[a] = b即可，即令1成為0的一個(gè)孩子
統(tǒng)計(jì)集合的個(gè)數(shù)：統(tǒng)計(jì)數(shù)組中元素為負(fù)數(shù)的個(gè)數(shù)

二、并查集的實(shí)現(xiàn)

#pragma once
#include<vector>
#include<iostream>
using namespace std;

class UnionFindSet
{
public:
	UnionFindSet(int size)
		:_set(size, -1) // 初始時(shí)每個(gè)數(shù)據(jù)各是一棵樹，元素均為-1
	{ }

	// 查找一個(gè)數(shù)據(jù)屬于哪個(gè)集合，找根元素的下標(biāo)
	int FindRoot(int i)
	{
		while (_set[i] >= 0)
		{
			i = _set[i];
		}
		return i;
	}

	// 合并兩個(gè)數(shù)據(jù)所在的集合
	void Union(int i1, int i2)
	{
		// 找這兩個(gè)數(shù)據(jù)的根下標(biāo)
		int root1 = FindRoot(i1);
		int root2 = FindRoot(i2);

		if (root1 != root2)
		{
			_set[root1] += _set[root2];
			_set[root2] = root1;
		}

		// 如果root1 == root2，說明這兩個(gè)數(shù)據(jù)本就在一個(gè)集合，不用合并

	}

	// 判斷兩個(gè)數(shù)據(jù)是否在同一個(gè)集合
	bool IsSameSet(int i1, int i2)
	{
		return FindRoot(i1) == FindRoot(i2);
	}

	// 統(tǒng)計(jì)集合個(gè)數(shù)
	int SetCount()
	{
		int ret = 0;
		for (int n : _set)
		{
			if (n < 0)
				ret++;
		}
		return ret;
	}

private:
	vector<int> _set;
};

測(cè)試：

三、算法題中的應(yīng)用

并查集的特點(diǎn)在某些算法題中很有用：

省份數(shù)量

class Solution {
public:
    // 并查集, 統(tǒng)計(jì)集合數(shù)量
    int findCircleNum(vector<vector<int>>& isConnected) {
        vector<int> ufs(isConnected.size(), -1);
        auto findRoot = [&ufs](int i)
        {
            while(ufs[i] >= 0)
            {
                i = ufs[i];
            }
            return i;
        };
        auto Union = [&ufs, &findRoot](int i1, int i2)
        {
            int root1 = findRoot(i1);
            int root2 = findRoot(i2);
            if(root1 != root2)
            {
                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
            }
        };
        auto SetCount = [&ufs]()
        {
            int ret = 0;
            for(int n : ufs)
            {
                if(n < 0)
                    ret++;
            }
            return ret;
        };

        for(int i = 0; i < isConnected.size(); i++)
        {
            for(int j = 0; j < isConnected[i].size(); j++)
            {
                if(isConnected[i][j] == 1)
                {
                    Union(i, j);
                }
            }
        }
        return SetCount();
    }
};

等式方程的可滿足性

class Solution {
public:
    // 并查集，數(shù)組大小26
    // 遍歷一次把所有==的兩個(gè)字母放到一個(gè)集合，再遍歷一次看!=的兩個(gè)字符是否都在集合中出現(xiàn)過，出現(xiàn)過則false
    bool equationsPossible(vector<string>& equations) {
        vector<int> ufs(26, -1);
        auto findRoot = [&ufs](int i)
        {
            while(ufs[i] >= 0)
            {
                i = ufs[i];
            }
            return i;
        };
        auto Union = [&ufs, &findRoot](int i1, int i2)
        {
            int root1 = findRoot(i1);
            int root2 = findRoot(i2);
            if(root1 != root2)
            {
                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
            }
        };

        for(string& s : equations)
        {
            if(s[1] == '=')
            {
                Union(s[0]-'a', s[3]-'a');
            }
        }
        
        for(string& s : equations)
        {
            if(s[1] == '!')
            {
                int root1 = findRoot(s[0]-'a');
                int root2 = findRoot(s[3]-'a');
                if(root1 == root2)
                {
                    return false;
                }
            }
        }

        return true;
    }
};