2021-1 并查集 c++_综合

union_find API

UF(int n) 构造函数，初始化n个空间
bool connected（int v, int w）判断是否连通
int find（int p) 找到p所在集合的根
void Union(int v,int w) 合并两个集合,大写首字母为了区别关键字union

代码

//UF.h
#pragma once
#include<vector>
#include<iostream>
using namespace std;
class UF
{
    
public:UF(int n);bool connected(int w, int v);void Union(int w, int v);int find(int p);int count() {
     return m_count; }
private:vector<int>* m_parent = nullptr;// parent[i] = parent of ivector<int>* m_rank = nullptr;// rank[i] = rank of subtree rooted at i int m_count=0;// number of componentsvoid validate(int p);
};

#include "UF.h"UF::UF(int n)
{
    if (n < 0) {
    printf_s("n needs > 0.\n");return;}m_parent = new vector<int>(n);m_rank = new vector<int>(n,0);for (int i = 0; i < n; ++i) {
    m_parent->at(i) = i;}
}bool UF::connected(int w, int v)
{
    return find(w)==find(v);
}void UF::Union(int w, int v)
{
    int rootW = find(w);int rootV = find(v);if (rootW == rootV) return;//同一集合，不用合并//把rank理解为合并次数，次数多的，集合大，并让小的依附大的if (m_rank->at(rootW) < m_rank->at(rootV)) {
    m_parent->at(rootW) = rootV;}else if (m_rank->at(rootW) > m_rank->at(rootV)) {
    m_parent->at(rootV) = rootW;}else {
    m_parent->at(rootV) = rootW;m_rank->at(rootW)++;}m_count--;
}int UF::find(int p)
{
    validate(p);while (p != m_parent->at(p)) {
    // 路径折半压缩m_parent->at(p) = (*m_parent)[m_parent->at(p)];p = m_parent->at(p);}return p;
}void UF::validate(int p) {
    int n = m_parent->size();if (p < 0 || p >= n) {
    cout<<"index " << p << " is not between 0 and " + (n - 1)<<endl;}
}