【算法日志】圖論: 并查集及其簡(jiǎn)單應(yīng)用

并查集概論

并查集是一種算法設(shè)計(jì)思想，通過判斷兩個(gè)元素是否在同一個(gè)集合里，常用來解決一些和圖相關(guān)的連通性問題。

并查集主要有以下兩個(gè)功能：

• 將兩個(gè)元素添加到一個(gè)集合中。
• 判斷兩個(gè)元素是否是在一個(gè)集合之中(這一功能夠有效判斷是否成環(huán))。

主要思想：

通過創(chuàng)建一個(gè)數(shù)組用來保每個(gè)點(diǎn)的最老根節(jié)點(diǎn)，以此來實(shí)現(xiàn)并查集的各種功能。

具體模板如下：

int n = 1005; // n根據(jù)題目中節(jié)點(diǎn)數(shù)量而定，一般比節(jié)點(diǎn)數(shù)量大一點(diǎn)就好
vector<int> father = vector<int> (n, 0); // C++里的一種數(shù)組結(jié)構(gòu)
// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里尋根的過程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路徑壓縮
}
// 判斷 u 和 v是否找到同一個(gè)根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}
// 將v->u 這條邊加入并查集
void join(int u, int v) {
    u = find(u); // 尋找u的根
    v = find(v); // 尋找v的根
    if (u == v) return ; // 如果發(fā)現(xiàn)根相同，則說明在一個(gè)集合，不用兩個(gè)節(jié)點(diǎn)相連直接返回
    father[v] = u;
}

簡(jiǎn)單應(yīng)用

leetcode 1971:尋找是否存在路徑

本題是雙向圖，只要始末點(diǎn)相連就存在有效路徑，因此只需要將合并樹，判斷始末節(jié)點(diǎn)的最老根節(jié)點(diǎn)是否一樣就行。

具體示例代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-818364.html

	void Init(vector<int>& f, const int& n)
	{
		for (int i = 0; i < n; ++i)
			f[i] = i;
	}
	int find(vector<int>& f, int v)
	{
		return v == f[v] ? v : find(f, f[v]);
	}
	bool isSame(vector<int>& f, int v, int u)
	{
		v = find(f, v);
		u = find(f, u);
		return v == u;
	}
	void join(vector<int>& f, int v, int u)
	{
		v = find(f, v);
		u = find(f, u);
		if (v != u)
			f[u] = v;
	}

	bool validPath(int n, vector<vector<int>>& edges, int source, int destination)
	{
		vector<vector<int>> path;
		vector<int> father(n + 1, 0);
		Init(father, n + 1);
		int size = edges.size();
		for (int i = 0; i < size; ++i)
			join(father, edges[i][0], edges[i][1]);
		return isSame(father, source, destination);
	}

leetcode 648: 冗余連接

本題要連接的點(diǎn)在連接前存在共同根節(jié)點(diǎn)，那么連接該兩點(diǎn)就會(huì)形成環(huán)路，因此需要移除的邊就是以這兩點(diǎn)為端點(diǎn)的邊。

具體示例代碼如下：

	void Init(vector<int>& f, const int& n)
	{
		for (int i = 0; i < n; ++i)
			f[i] = i;
	}
	int find(vector<int>& f, int v)
	{
		return v == f[v] ? v : find(f, f[v]);
	}
	bool isSame(vector<int>& f, int v, int u)
	{
		v = find(f, v);
		u = find(f, u);
		return v == u;
	}
	void join(vector<int>& f, int v, int u)
	{
		v = find(f, v);
		u = find(f, u);
		if (v != u)
			f[u] = v;
	}
	vector<int> findRedundantConnection(vector<vector<int>>& edges)
	{
		int n = edges.size();
		vector<int> father(n + 1, 0);
		Init(father, n + 1);
		for (int i = 0; i < n; ++i)
		{
			if (isSame(father, edges[i][0], edges[i][1]))
				return { edges[i][0], edges[i][1] };
			join(father, edges[i][0], edges[i][1]);
		}
		return {};
	}

到了這里，關(guān)于【算法日志】圖論 并查集及其簡(jiǎn)單應(yīng)用的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！