C++ の動作確認をしてみた（６４３）

C++の練習を兼ねて, AtCoder Beginner Contest 120 の問題D (Decayed Bridges) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達できたと思う.
2. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 120 解説の各リンクをご覧下さい.

■C++版プログラム(問題D／AC版).

// 解き直し.
// https://img.atcoder.jp/abc120/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
LL ans[101010];
int a[101010], b[101010];

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vi d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, M){
        scanf("%d %d", &a[i], &b[i]);
        --a[i];
        --b[i];
    }
    
    // 2. 不便さは？
    ans[M] = (LL)N * (LL)(N - 1) / 2;
    UnionFind uf(N + 2);
    repr(i, M - 1, 0){
        // 2-1. 頂点情報.
        int u = a[i];
        int v = b[i];
        
        // 2-2. 連結だった.
        // -> 不便さ変わらない.
        if(uf.same(u, v)) ans[i] = ans[i + 1];
        
        // 2-3. 連結でなかった.
        if(!uf.same(u, v)){
            // グループ番号.
            int g1 = uf.find(u);
            int g2 = uf.find(v);
            
            // グループサイズ.
            LL n1 = (LL)uf.size(g1);
            LL n2 = (LL)uf.size(g2);
            
            // 不便さ更新.
            ans[i] = ans[i + 1] - n1 * n2;
            
            // 連結.
            uf.unite(u, v);
        }
    }
    
    // 3. 出力.
    repx(i, 1, M + 1) printf("%lld\n", ans[i]);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc120/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using LL = long long;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

LL ans[101010];

int a[101010], b[101010];

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vi d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

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

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

rep(i, M){

scanf("%d %d", &a[i], &b[i]);

--a[i];

--b[i];

}

// 2. 不便さは？

ans[M] = (LL)N * (LL)(N - 1) / 2;

UnionFind uf(N + 2);

repr(i, M - 1, 0){

// 2-1. 頂点情報.

int u = a[i];

int v = b[i];

// 2-2. 連結だった.

// -> 不便さ変わらない.

if(uf.same(u, v)) ans[i] = ans[i + 1];

// 2-3. 連結でなかった.

if(!uf.same(u, v)){

// グループ番号.

int g1 = uf.find(u);

int g2 = uf.find(v);

// グループサイズ.

LL n1 = (LL)uf.size(g1);

LL n2 = (LL)uf.size(g2);

// 不便さ更新.

ans[i] = ans[i + 1] - n1 * n2;

// 連結.

uf.unite(u, v);

}

// 3. 出力.

repx(i, 1, M + 1) printf("%lld\n", ans[i]);

return 0;

}

[入力例]
4 5
1 2
3 4
1 3
2 3
1 4

[出力例]
0
0
4
5
6
※AtCoderテストケースより

[入力例]
6 5
2 3
1 2
5 6
3 4
4 5

[出力例]
8
9
12
14
15
※AtCoderテストケースより

[入力例]
2 1
1 2

[出力例]
1
※AtCoderテストケースより

[入力例]
7 6
1 2
1 3
2 4
3 5
4 6
6 7

[出力例]
12
14
17
18
20
21

[入力例]
10 9
1 2
3 4
2 5
5 7
5 6
6 8
8 9
6 10
3 6

[出力例]
9
17
24
30
35
41
42
44
45

[入力例]

4 5

1 2

3 4

1 3

2 3

1 4

[出力例]

※AtCoderテストケースより

[入力例]

6 5

2 3

1 2

5 6

3 4

4 5

[出力例]

※AtCoderテストケースより

[入力例]

2 1

1 2

[出力例]

※AtCoderテストケースより

[入力例]

7 6

1 2

1 3

2 4

3 5

4 6

6 7

[出力例]

[入力例]

10 9

1 2

3 4

2 5

5 7

5 6

6 8

8 9

6 10

3 6

[出力例]

■参照サイト
AtCoder Beginner Contest 120
Union-Find木

C++の練習を兼ねて, AtCoder Beginner Contest 120 の 問題D (Decayed Bridges) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 120 の問題D (Decayed Bridges) を解いてみた.

コメントを残すコメントをキャンセル