C++ の動作確認をしてみた（６２８）

C++の練習を兼ねて, AtCoder Beginner Contest 235 の問題E (MST + 1) を解いてみた.

■感想.
1. 問題Eは, 方針を絞ることが出来たので, AC版に到達できたと思う.
2. 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 235 解説をご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using T4 = tuple<int, int, int, int>;
#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--)
#define all(x) x.begin(), x.end()

// 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, Q;
    scanf("%d %d %d", &N, &M, &Q);
    vector<T4> t;
    rep(i, M + Q){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a--, b--;
        t.emplace_back(c, a, b, (i < M) ? 0 : (i - M + 1));
    }
    
    // 2. sort.
    sort(all(t));
    
    // 3. 最小全域木(Kruskal's Algorithm) の 構築.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    int ans[Q];
    rep(i, Q) ans[i] = 0;
    UnionFind uf(N + 2);
    rep(i, t.size()){
        // 3-1. グラフ情報.
        int u = get<1>(t[i]); // 頂点.
        int v = get<2>(t[i]); // 頂点.
        int q = get<3>(t[i]); // グラフG(0) or クエリ番号(1, 2, ...).
        
        // 3-2. 最小全域木を構成する辺の追加.
        // -> 但し, クエリ情報の場合は, 辺は追加しない.
        if(!uf.same(u, v)){
            if(q) ans[q - 1] = 1;
            else  uf.unite(u, v);
        }
    }
    
    // 4. 出力.
    rep(i, Q) printf("%s\n", ans[i] ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using T4 = tuple<int, int, int, int>;

#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--)

#define all(x) x.begin(), x.end()

// 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, Q;

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

vector<T4> t;

rep(i, M + Q){

int a, b, c;

scanf("%d %d %d", &a, &b, &c);

a--, b--;

t.emplace_back(c, a, b, (i < M) ? 0 : (i - M + 1));

}

// 2. sort.

sort(all(t));

// 3. 最小全域木(Kruskal's Algorithm) の構築.

// 競プロ典型 90 問 (049 - Flip Digits 2)

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp

int ans[Q];

rep(i, Q) ans[i] = 0;

UnionFind uf(N + 2);

rep(i, t.size()){

// 3-1. グラフ情報.

int u = get<1>(t[i]); // 頂点.

int v = get<2>(t[i]); // 頂点.

int q = get<3>(t[i]); // グラフG(0) or クエリ番号(1, 2, ...).

// 3-2. 最小全域木を構成する辺の追加.

// -> 但し, クエリ情報の場合は, 辺は追加しない.

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

if(q) ans[q - 1] = 1;

else uf.unite(u, v);

}

// 4. 出力.

rep(i, Q) printf("%s\n", ans[i] ? "Yes" : "No");

return 0;

}

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

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

[入力例]
2 3 2
1 2 100
1 2 1000000000
1 1 1
1 2 2
1 1 5

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

[入力例]
6 12 6
1 2 7
1 4 3
6 1 5
6 1 2
1 1 8
2 5 12
2 3 5
6 5 10
5 4 6
5 4 11
4 3 13
3 2 5
1 3 5
2 4 20
3 5 7
4 6 18
5 1 3
1 2 3

[出力例]
Yes
No
No
No
Yes
Yes

[入力例]
10 15 10
1 2 8
9 1 2
9 6 6
2 6 1
1 5 5
2 3 2
5 3 3
5 7 11
5 10 12
7 10 8
7 4 7
3 4 1
4 8 4
3 8 10
8 10 5
1 3 5
5 4 2
7 8 17
9 6 12
3 5 6
5 9 4
6 8 7
9 8 3
1 7 10
7 2 6

[出力例]
Yes
Yes
No
No
No
Yes
No
Yes
No
Yes

[入力例]

5 6 3

1 2 2

2 3 3

1 3 6

2 4 5

4 5 9

3 5 8

1 3 1

3 4 7

3 5 7

[出力例]

Yes

※AtCoderテストケースより

[入力例]

2 3 2

1 2 100

1 2 1000000000

1 1 1

1 2 2

1 1 5

[出力例]

Yes

※AtCoderテストケースより

[入力例]

6 12 6

1 2 7

1 4 3

6 1 5

6 1 2

1 1 8

2 5 12

2 3 5

6 5 10

5 4 6

5 4 11

4 3 13

3 2 5

1 3 5

2 4 20

3 5 7

4 6 18

5 1 3

1 2 3

[出力例]

Yes

[入力例]

10 15 10

1 2 8

9 1 2

9 6 6

2 6 1

1 5 5

2 3 2

5 3 3

5 7 11

5 10 12

7 10 8

7 4 7

3 4 1

4 8 4

3 8 10

8 10 5

1 3 5

5 4 2

7 8 17

9 6 12

3 5 6

5 9 4

6 8 7

9 8 3

1 7 10

7 2 6

[出力例]

Yes

■参照サイト
HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）
Union-Find木
 競プロ典型 90 問の問題049

C++の練習を兼ねて, AtCoder Beginner Contest 235 の 問題E (MST + 1) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 235 の問題E (MST + 1) を解いてみた.

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