algorithm/source/islandNum.cpp at main · butcher-x/algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//
// Created by ButcherX on 23-11-5.
//
//方法一：并查集
#include<vector>
using std::vector;
class UnionFind {
public:
    UnionFind(vector<vector<char>>& grid)
    {
        counts = 0;
        int r = grid.size();
        int c = grid[0].size();
        parent.resize(r*c);
        size.resize(r*c, 0);
        for (int i = 0; i < r*c; i++)
        {
            parent[i] = i;
            size[i] = 1;
        }
        for (int i = 0; i < r; i++)
        {
            for(int k = 0; k < c; k++)
            {
                if(grid[i][k] == '1')
                    counts++;
            }
        }
    }

    int find(int x)
    {
        int anc = x;
        int tmp;
        while(anc != parent[anc])
            anc = parent[anc];
        while(x != anc)
        {
            tmp = x;
            x = parent[x];
            parent[tmp] = anc;
        }
        return anc;
    }

    void unite(int x, int y)
    {
        int px = find(x);
        int py = find(y);
        if (px == py)
            return;
        if (size[px] < size[py])
        {
            parent[px] = py;
            size[py] += size[px];
            size[px] = 0;
        }
        else
        {
            parent[py] = px;
            size[px] += size[py];
            size[py] = 0;
        }
        counts--;
    }
    bool isSameSet(int x, int y)
    {
        return find(x) == find(y);
    }
    int count()
    {
        return counts;
    }

private:
    vector<int> parent;
    vector<int> size;
    int counts;
};

int numIslands(vector<vector<char>>& grid)
{
    UnionFind uf(grid);
    int r = grid.size();
    int c = grid[0].size();
    for(int i = 0; i < r; i++)
    {
        for(int k = 0; k < c; k++)
        {
            if(i - 1 >= 0 && grid[i][k] == '1' && grid[i-1][k] == '1')
                uf.unite(i * c + k, i * c + k - c);
            if(k - 1 >= 0 && grid[i][k] == '1' && grid[i][k-1] == '1')
                uf.unite(i * c + k, i * c + k - 1);
        }
    }
    return uf.count();
}
//方法二：感染