#617963 (C++14) No.1390 Get together

• 問題: No.1390 Get together
• ユーザー: misora192
• 提出日時: 2021-02-14 21:15:19
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 406 ms / 2,000 ms
• コード長: 1,858 bytes
• コンパイル時間: 1,744 ms
• コンパイル使用メモリ: 188,480 KB
• 実行使用メモリ: 28,544 KB
• 最終ジャッジ日時: 2024-07-22 08:22:07
• 合計ジャッジ時間: 8,242 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 29

ソースコード

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
99
100
101
102
103
104
105
#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
using namespace std;
typedef long long ll;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
// union-find tree with size(struct)
struct UnionFind{
    vector<int> par; // 親ノード
    vector<int> rank; // ランク
    vector<int> size; // 連結成分のサイズ
    UnionFind(int n = 1) {
        init(n);
    }
    void init(int n = 1) {
        par.resize(n);
        rank.resize(n);
        size.resize(n);
        for (int i = 0; i < n; ++i){
            par[i] = i;
            rank[i] = 0;
            size[i] = 1;
        }
    }
    int find(int x) {
        if (par[x] == x)  return x;
        int r = find(par[x]);
        return par[x] = r;
    }
    bool issame(int x, int y) {
        return find(x) == find(y);
    }
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        size[x] += size[y];
        return true;
    }
    int getSize(int x){
        return size[find(x)];
    }
    int getRank(int x){
        return rank[find(x)];
    }
};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<int> b(N), c(N);
    rep(i, N) {
        cin >> b[i] >> c[i];
        b[i]--;
        c[i]--;
    }
    int col = 0;
    map<int, int> cmap;
    rep(i, N){
        if(cmap.count(c[i]) == 0){
            cmap[c[i]] = col;
            col++;
        }
    }
    UnionFind uf(col);
    map<int, vector<int>> bmap;
    rep(i, N){
        if(bmap.count(b[i]) == 0){
            bmap[b[i]].push_back(cmap[c[i]]);
        }else{
            uf.unite(bmap[b[i]].back(), cmap[c[i]]);
            bmap[b[i]].push_back(cmap[c[i]]);
        }
    }
    int box = bmap.size();
    set<int> st;
    rep(i, col) st.insert(uf.find(i));
    cout << box - st.size() << endl;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX