Counting Islands II

Description:
Counting Islands II

分析：

思路：

Code:

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
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

using namespace std;

//typedef pair<int, int> pii;
//typedef long long LL;

const int MAX = 1010;
int pre[MAX * MAX];
int grip[MAX][MAX];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

void clear() {
    memset(pre, -1, sizeof(pre));
    memset(grip, 0, sizeof(grip));
}

int findPre(int x) {
    if (pre[x] == -1) {
        return pre[x] = x;
    }
    
    return pre[x] == x ? pre[x] : findPre(pre[x]);
}

void unionSet(int x, int y) {
    int fx = findPre(x);
    int fy = findPre(y);
    
    if (fx != fy) {
        pre[fx] = fy;
    }
}

int main() {
    clear();
    int cnt = 0;
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        
        cnt++;
        grip[x][y] = 1;
        
        for (int j = 0; j < 4; j++) {
            int nx = x + dx[j];
            int ny = y + dy[j];
            
            if (0 <= nx && nx < 1000 && 0 <= ny && ny < 1000) {
                if (grip[nx][ny] == 1 && findPre(nx * 1000 + ny) != findPre(x * 1000 + y)) {
                    cnt--;
                    unionSet(nx * 1000 + ny, x * 1000 + y);
                }
            }
        }
        
        printf("%d\n", cnt);
    }
    
    return 0;
}