UnionFind类 参考

并查集 更多...

#include <templates.h>

Public 成员函数
	UnionFind (int n)
unsigned	count ()
int	find (int x)
int	get_size (int x)
bool	same (int x, int y)
void	unite (int x, int y)

Private 属性
vector< int >	parent
vector< int >	rank
vector< int >	size

详细描述

并查集

在文件 templates.h 第 91 行定义.

构造及析构函数说明

UnionFind()

UnionFind::UnionFind ( int  n )

explicit

在文件 templates.cpp 第 478 行定义.

                          {
    this->parent = vector<int>(n);
    this->rank   = vector<int>(n);
    this->size   = vector<int>(n);
    for(int i = 0; i < n; i++) {
        this->parent[i] = i;
        this->rank[i]   = 0;
        size[i]         = 1;
    }
}

引用了 parent, rank , 以及 size.

成员函数说明

count()

unsigned UnionFind::count

(

)

在文件 templates.cpp 第 518 行定义.

                          {
    unordered_set<int> us;
    for(int i = 0; i < size.size(); i++) {
        us.insert(find(i));
    }
    return us.size();
}

引用了 find() , 以及 size.

find()

int UnionFind::find

(

int

x

)

在文件 templates.cpp 第 489 行定义.

                         {
    if(parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

引用了 find() , 以及 parent.

被这些函数引用 count(), find(), leetcode::process_restricted_friend_requests::Solution::friendRequests(), get_size(), pat::a::a1021::main(), same() , 以及 unite().

get_size()

int UnionFind::get_size

(

int

x

)

在文件 templates.cpp 第 516 行定义.

{ return size[find(x)]; }

引用了 find() , 以及 size.

被这些函数引用 acwing::acwing837::main().

same()

bool UnionFind::same	(	int	x,
		int	y
	)

在文件 templates.cpp 第 514 行定义.

{ return find(x) == find(y); }

引用了 find().

被这些函数引用 acwing::acwing837::main() , 以及 acwing::acwing859::main().

unite()

void UnionFind::unite	(	int	x,
		int	y
	)

在文件 templates.cpp 第 496 行定义.

                                  {
    x = find(x);
    y = find(y);
    if(x == y) {
        return;
    }
    if(rank[x] < rank[y]) {
        parent[x] = y;
        size[y] += size[x];
    } else {
        parent[y] = x;
        size[x] += size[y];
        if(rank[x] == rank[y]) {
            rank[x]++;
        }
    }
}

引用了 find(), parent, rank , 以及 size.

被这些函数引用 leetcode::process_restricted_friend_requests::Solution::friendRequests(), acwing::acwing837::main(), acwing::acwing859::main() , 以及 pat::a::a1021::main().

类成员变量说明

parent

vector<int> UnionFind::parent

private

在文件 templates.h 第 93 行定义.

被这些函数引用 UnionFind(), find() , 以及 unite().

rank

vector<int> UnionFind::rank

private

在文件 templates.h 第 94 行定义.

被这些函数引用 UnionFind() , 以及 unite().

size

vector<int> UnionFind::size

private

在文件 templates.h 第 95 行定义.

被这些函数引用 UnionFind(), count(), get_size() , 以及 unite().

---

该类的文档由以下文件生成:

• templates.h
• templates.cpp