leetcode::max_area_of_island::UnionFind类 参考

#include <leetcode.h>

Public 成员函数
	UnionFind (int m, int n)
bool	contains (pair< int, int > p) const
pair< int, int >	find (pair< int, int > val)
int	get_size (pair< int, int > p)
void	merge (pair< int, int > a, pair< int, int > b)
bool	same (pair< int, int > a, pair< int, int > b)

Private 属性
int	m
int	n
unordered_map< pair< int, int >, pair< int, int >, function< unsigned int(const pair< int, int > &)> >	parent
unordered_map< pair< int, int >, int, function< unsigned int(const pair< int, int > &)> >	rank
unordered_map< pair< int, int >, int, function< unsigned int(const pair< int, int > &)> >	size

详细描述

在文件 leetcode.h 第 1665 行定义.

构造及析构函数说明

UnionFind()

UnionFind::UnionFind	(	int	m,
		int	n
	)

在文件 leetcode.cpp 第 4255 行定义.

            : m(m), n(n) {
            parent = unordered_map<pair<int, int>,
                                   pair<int, int>,
                                   function<unsigned int(const pair<int, int> &)>>(
                    m * n,
                    [](const pair<int, int> &p) { return static_cast<unsigned int>(p.first * 50 + p.second); });
            size = unordered_map<pair<int, int>,
                                 int,
                                 function<unsigned int(const pair<int, int> &)>>(
                    m * n,
                    [](const pair<int, int> &p) { return static_cast<unsigned int>(p.first * 50 + p.second); });
            rank = unordered_map<pair<int, int>,
                                 int,
                                 function<unsigned int(const pair<int, int> &)>>(
                    m * n,
                    [](const pair<int, int> &p) { return static_cast<unsigned int>(p.first * 50 + p.second); });
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    pair<int, int> p = make_pair(i, j);
                    parent[p]        = p;
                    size[p]          = 1;
                    rank[p]          = 0;
                }
            }
        }

引用了 m, n, parent, rank , 以及 size.

成员函数说明

contains()

bool UnionFind::contains

(

pair< int, int >

p

)

const

在文件 leetcode.cpp 第 4309 行定义.

{ return parent.contains(p); }

引用了 parent.

find()

pair< int, int > UnionFind::find

(

pair< int, int >

val

)

在文件 leetcode.cpp 第 4282 行定义.

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

引用了 find() , 以及 parent.

被这些函数引用 find(), get_size(), merge() , 以及 same().

get_size()

int UnionFind::get_size

(

pair< int, int >

p

)

在文件 leetcode.cpp 第 4311 行定义.

{ return size[find(p)]; }

引用了 find() , 以及 size.

merge()

void UnionFind::merge	(	pair< int, int >	a,
		pair< int, int >	b
	)

在文件 leetcode.cpp 第 4289 行定义.

                                                                {
            const auto pa = find(a);
            const auto pb = find(b);
            if(pa != pb) {
                const int sum = size[pa] + size[pb];
                if(rank[pa] > rank[pb]) {
                    parent[pb] = pa;
                } else {
                    parent[pa] = pb;
                    if(rank[pa] == rank[pb]) {
                        ++rank[pb];
                    }
                }
                size[pa] = sum;
                size[pb] = sum;
            }
        }

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

same()

bool UnionFind::same	(	pair< int, int >	a,
		pair< int, int >	b
	)

在文件 leetcode.cpp 第 4307 行定义.

{ return find(a) == find(b); }

引用了 find().

类成员变量说明

m

int leetcode::max_area_of_island::UnionFind::m

private

在文件 leetcode.h 第 1667 行定义.

被这些函数引用 UnionFind().

n

int leetcode::max_area_of_island::UnionFind::n

private

在文件 leetcode.h 第 1668 行定义.

被这些函数引用 UnionFind().

parent

unordered_map<pair<int, int>, pair<int, int>, function<unsigned int(const pair<int, int> &)> > leetcode::max_area_of_island::UnionFind::parent

private

在文件 leetcode.h 第 1669 行定义.

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

rank

unordered_map<pair<int, int>, int, function<unsigned int(const pair<int, int> &)> > leetcode::max_area_of_island::UnionFind::rank

private

在文件 leetcode.h 第 1671 行定义.

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

size

unordered_map<pair<int, int>, int, function<unsigned int(const pair<int, int> &)> > leetcode::max_area_of_island::UnionFind::size

private

在文件 leetcode.h 第 1670 行定义.

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

---

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

• leetcode.h
• leetcode.cpp