C++并查集

qq_43355454

182人浏览 · 2025-11-07 20:28:50

qq_43355454 · 2025-11-07 20:28:50 发布

并查集：朴素算法代码框架见下

#include<iostream>
#include<unordered_map>
using namespace std;

//并：合并
//查：查找
//集：集合

class UFSetsample {
public:
	void Init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
private:
	unordered_map<int, int> m_set;
};

void UFSetsample::Init(int maxId)
{
	m_set.clear();
	for (int i = 1; i <= maxId; ++i) {
		m_set[i] = i;
	}
}

int UFSetsample::Find(int id)
{
	return m_set[id];
}

bool UFSetsample::Union(int id1, int id2)
{
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2) {
		return false; // 合并失败
	}
	int n = m_set.size();
	for (int i = 1; i <= n; ++i) {
		if (m_set[i] == s1) {
			m_set[i] = s2;
		}
	}
	return true; // 合并成功
}




int main() {
	int n, m;
	UFSetsample uf;
	cin >> n >> m;
	uf.Init(n);
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			uf.Union(b, c);
		}
		else {
			if (uf.Find(b) == uf.Find(c)) {
				cout << 'Y' << endl;
			}
			else {
				cout << 'N' << endl;
			}
		}
	}
	return 0;
}

并查集：森林算法代码框架见下

#include<iostream>
#include<unordered_map>
using namespace std;

//并：合并
//查：查找
//集：集合

class UFForest {
public:
	void Init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
private:
	unordered_map<int, int> m_far; //m_far[x] 代表在这棵树上x的父节点编号
};

void UFForest::Init(int maxId)
{
	m_far.clear();
	for (int i = 1; i <= maxId; ++i) {
		m_far[i] = i;
	}
}

int UFForest::Find(int id)
{
	int p = m_far[id];
	while (p != m_far[p]) {
		p = m_far[p];
	}
	return p;
}

bool UFForest::Union(int id1, int id2)
{
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2) {
		return false; // 合并失败
	}
	m_far[s1] = s2;
	return true; // 合并成功
}




int main() {
	int n, m;
	UFForest uf;
	cin >> n >> m;
	uf.Init(n);
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			uf.Union(b, c);
		}
		else {
			if (uf.Find(b) == uf.Find(c)) {
				cout << 'Y' << endl;
			}
			else {
				cout << 'N' << endl;
			}
		}
	}
	return 0;
}

C++ 并查集：启发式合并，代码框架见下

#include<iostream>
#include<unordered_map>
using namespace std;

//并：合并
//查：查找
//集：集合

class UFSetstar {
public:
	void Init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
private:
	unordered_map<int, int> m_far; //m_far[x] 代表在这棵树上x的父节点编号
	unordered_map<int, int> m_height; //m_height[x] 代表x为根的这棵树的高度
};

void UFSetstar::Init(int maxId)
{
	m_far.clear();
	m_height.clear();
	for (int i = 1; i <= maxId; ++i) {
		m_far[i] = i;
		m_height[i] = 1;
	}
}

int UFSetstar::Find(int id)
{
	int p = m_far[id];
	while (p != m_far[p]) {
		p = m_far[p];
	}
	return p;
}

bool UFSetstar::Union(int id1, int id2)
{
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2) {
		return false; // 合并失败
	}
	if (m_height[s1] < m_height[s2]) {
		m_far[s1] = s2;
	}
	else if (m_height[s2] < m_height[s1]) {
		m_far[s2] = s1;
	}
	else {
		m_far[s1] = s2;
		m_height[s2]++;
	}
	return true; // 合并成功
}




int main() {
	int n, m;
	UFSetstar uf;
	cin >> n >> m;
	uf.Init(n);
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			uf.Union(b, c);
		}
		else {
			if (uf.Find(b) == uf.Find(c)) {
				cout << 'Y' << endl;
			}
			else {
				cout << 'N' << endl;
			}
		}
	}
	return 0;
}

C++ 并查集：路径压缩代码框架见下

#include<iostream>
#include<unordered_map>
using namespace std;

//并：合并
//查：查找
//集：集合

class UFSet {
public:
	void Init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
private:
	unordered_map<int, int> m_far; //m_far[x] 代表在这棵树上x的父节点编号
};

void UFSet::Init(int maxId)
{
	m_far.clear();
	for (int i = 1; i <= maxId; ++i) {
		m_far[i] = i;
	}
}

int UFSet::Find(int id)
{
	if (m_far[id] == id) {
		return id;
	}
	m_far[id] = Find(m_far[id]);
	return m_far[id];
}

bool UFSet::Union(int id1, int id2)
{
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2) {
		return false; // 合并失败
	}
	m_far[s1] = s2;
	return true; // 合并成功
}




int main() {
	int n, m;
	UFSet uf;
	cin >> n >> m;
	uf.Init(n);
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			uf.Union(b, c);
		}
		else {
			if (uf.Find(b) == uf.Find(c)) {
				cout << 'Y' << endl;
			}
			else {
				cout << 'N' << endl;
			}
		}
	}
	return 0;
}

C++ 并查集 Kruskal 代码框架见下

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;

//并：合并
//查：查找
//集：集合

class UFSet {
public:
	void Init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
	int Size() const;
private:
	unordered_map<int, int> m_far; //m_far[x] 代表在这棵树上x的父节点编号
};

void UFSet::Init(int maxId)
{
	m_far.clear();
	for (int i = 1; i <= maxId; ++i) {
		m_far[i] = i;
	}
}

int UFSet::Find(int id)
{
	if (m_far[id] == id) {
		return id;
	}
	m_far[id] = Find(m_far[id]);
	return m_far[id];
}

bool UFSet::Union(int id1, int id2)
{
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2) {
		return false; // 合并失败
	}
	m_far[s1] = s2;
	return true; // 合并成功
}

int UFSet::Size() const
{

	return m_far.size();
}

template<typename T>
struct Edge {
	int u, v;
	T w;
};

template<typename T>
class Kruskal {
public:
	void Init(int maxId);
	void AddEdge(int u, int v, T w);
	T Solve();
private:
	UFSet m_ufs;
	vector<Edge<T>> m_edges;
};

template<typename T>
void Kruskal<T>::Init(int maxId)
{
	m_ufs.Init(maxId);
	m_edges.clear();
}

template<typename T>
void Kruskal<T>::AddEdge(int u, int v, T w)
{
	m_edges.push_back({u, v, w});
}

template<typename T>
bool cmp(const Edge<T>& a, const Edge<T>& b) {
	return a.w < b.w;
}

template<typename T>
T Kruskal<T>::Solve()
{
	T sum = 0;
	int edgeCount = 0;
	sort(m_edges.begin(), m_edges.end(), cmp<T>);
	for (int i = 0; i < m_edges.size(); ++i) {
		Edge<T>& e = m_edges[i];
		if (m_ufs.Union(e.u, e.v)) {
			sum += e.w;
			++edgeCount;
		}
	}
	if (edgeCount < m_ufs.Size() - 1) {
		return -1;
	}
	return sum;
}


int main() {
	int n, m;
	Kruskal<int> ks;
	cin >> n >> m;
	ks.Init(n);
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		ks.AddEdge(a, b, c);
	}
	int sum = ks.Solve();
	if (sum < 0) {
		cout << "orz" << endl;
	}
	else {
		cout << sum << endl;
	}
	return 0;
}

代码练习 1 对应蓝桥云课连通分量的个数

#include<iostream>
#include<unordered_map>
using namespace std;

//并：合并
//查：查找
//集：集合

class UFSet {
public:
	void Init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
private:
	unordered_map<int, int> m_far; //m_far[x] 代表在这棵树上x的父节点编号
};

void UFSet::Init(int maxId)
{
	m_far.clear();
	for (int i = 1; i <= maxId; ++i) {
		m_far[i] = i;
	}
}

int UFSet::Find(int id)
{
	if (m_far[id] == id) {
		return id;
	}
	m_far[id] = Find(m_far[id]);
	return m_far[id];
}

bool UFSet::Union(int id1, int id2)
{
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2) {
		return false; // 合并失败
	}
	m_far[s1] = s2;
	return true; // 合并成功
}




int main() {
	int n, m;
	UFSet ufs;
	cin >> n >> m;
	int count = n;
	ufs.Init(n);
	while (m--) {
		int a, b;
		cin >> a >> b;
		if (ufs.Union(a, b)) {
			count--;
		}
	}
	cout << count << endl;
	return 0;
}

代码练习 2 对应蓝桥云课修建公路代码见下

#include<iostream>
#include<unordered_map>
using namespace std;

//并：合并
//查：查找
//集：集合

class UFSet {
public:
	void Init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
private:
	unordered_map<int, int> m_far; //m_far[x] 代表在这棵树上x的父节点编号
};

void UFSet::Init(int maxId)
{
	m_far.clear();
	for (int i = 1; i <= maxId; ++i) {
		m_far[i] = i;
	}
}

int UFSet::Find(int id)
{
	if (m_far[id] == id) {
		return id;
	}
	m_far[id] = Find(m_far[id]);
	return m_far[id];
}

bool UFSet::Union(int id1, int id2)
{
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2) {
		return false; // 合并失败
	}
	m_far[s1] = s2;
	return true; // 合并成功
}




int main() {
	int n, m;
	UFSet ufs;
	cin >> n >> m;
	int count = n;
	ufs.Init(n);
	while (m--) {
		int a, b;
		cin >> a >> b;
		if (ufs.Union(a, b)) {
			count--;
		}
	}
	if(count <= 3){
    cout << 0 << endl;
  }else{
    cout << count - 3 << endl;
  }
	return 0;
}

代码练习3 对应蓝桥云课修建公路1 代码见下

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;

//并：合并
//查：查找
//集：集合

class UFSet {
public:
	void Init(int maxId);
	int Find(int id);
	bool Union(int id1, int id2);
	int Size() const;
private:
	unordered_map<int, int> m_far; //m_far[x] 代表在这棵树上x的父节点编号
};

void UFSet::Init(int maxId)
{
	m_far.clear();
	for (int i = 1; i <= maxId; ++i) {
		m_far[i] = i;
	}
}

int UFSet::Find(int id)
{
	if (m_far[id] == id) {
		return id;
	}
	m_far[id] = Find(m_far[id]);
	return m_far[id];
}

bool UFSet::Union(int id1, int id2)
{
	int s1 = Find(id1), s2 = Find(id2);
	if (s1 == s2) {
		return false; // 合并失败
	}
	m_far[s1] = s2;
	return true; // 合并成功
}

int UFSet::Size() const
{

	return m_far.size();
}

template<typename T>
struct Edge {
	int u, v;
	T w;
};

template<typename T>
class Kruskal {
public:
	void Init(int maxId);
	void AddEdge(int u, int v, T w);
	T Solve();
private:
	UFSet m_ufs;
	vector<Edge<T>> m_edges;
};

template<typename T>
void Kruskal<T>::Init(int maxId)
{
	m_ufs.Init(maxId);
	m_edges.clear();
}

template<typename T>
void Kruskal<T>::AddEdge(int u, int v, T w)
{
	m_edges.push_back({ u, v, w });
}

template<typename T>
bool cmp(const Edge<T>& a, const Edge<T>& b) {
	return a.w < b.w;
}

template<typename T>
T Kruskal<T>::Solve()
{
	T sum = 0;
	int edgeCount = 0;
	sort(m_edges.begin(), m_edges.end(), cmp<T>);
	for (int i = 0; i < m_edges.size(); ++i) {
		Edge<T>& e = m_edges[i];
		if (m_ufs.Union(e.u, e.v)) {
			sum += e.w;
			++edgeCount;
		}
	}
	if (edgeCount < m_ufs.Size() - 1) {
		return -1;
	}
	return sum;
}


int main() {
	int n, m;
	Kruskal<long long> ks;
	cin >> n >> m;
	ks.Init(n);
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		ks.AddEdge(a, b, c);
	}
	cout << ks.Solve() << endl;
	return 0;
}

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

AI 语音分离模型商用部署：人声 / 背景音乐精准分割低延迟推理方案

AI Agent技术社区

基于BP神经网络的语音特征信号分类研究（Matlab代码实现）

语音信号分类是语音信号处理领域的核心研究方向，广泛应用于语音识别、声纹认证、语音情感分析、智能人机交互等诸多领域。由于语音信号具有非线性、时变性、随机性的复杂特征，传统分类方法难以精准挖掘语音特征与信号类别之间的关联关系，存在分类精度低、抗干扰能力弱、泛化性差等问题。BP神经网络凭借其强大的非线性映射、自适应学习和容错能力，能够有效适配复杂语音特征数据的分类任务。