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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題G (連結) を解いてみた.

■感想.
1. 問題Gは, 方針を絞り込めたので, AC版に到達できた.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<set<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--)

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    vs G(N);
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vs &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]){
                // 訪問済であれば, 処理をスキップ.
                if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
    };
    
    // 3. クエリ回答.
    rep(i, Q){
        int t, u, v;
        scanf("%d %d %d", &t, &u, &v);
        u--, v--;
        
        if(t == 1){
            // 辺(u, v)があるか？
            if(G[u].count(v) && G[v].count(u)){
                G[u].erase(v);
                G[v].erase(u);
            }else{
                G[u].insert(v);
                G[v].insert(u);
            }
        }
        
        if(t == 2){
            // 頂点 u から 頂点 v へ 辿れるか？
            int d[N];
            rep(i, N) d[i] = 0;
            bfs(G, u, d);
            
            // 出力.
            printf("%s\n", d[v] ? "Yes" : "No");
        }
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<set<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--)

int main(){

// 1. 入力情報.

int N, Q;

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

vs G(N);

// 2. bfs.

// https://ja.wikipedia.org/wiki/幅優先探索

auto bfs = [&](vs &G, int s, int* d){

// 空のキュー.

queue<int> q;

// 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// キューから取り出す.

int u = q.front();

q.pop();

// 取り出した要素を処理.

for(auto &e : G[u]){

// 訪問済であれば, 処理をスキップ.

if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);

}

};

// 3. クエリ回答.

rep(i, Q){

int t, u, v;

scanf("%d %d %d", &t, &u, &v);

u--, v--;

if(t == 1){

// 辺(u, v)があるか？

if(G[u].count(v) && G[v].count(u)){

G[u].erase(v);

G[v].erase(u);

}else{

G[u].insert(v);

G[v].insert(u);

}

if(t == 2){

// 頂点 u から頂点 v へ辿れるか？

int d[N];

rep(i, N) d[i] = 0;

bfs(G, u, d);

// 出力.

printf("%s\n", d[v] ? "Yes" : "No");

}

return 0;

}

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

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

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

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

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

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

[入力例]

3 5

1 1 2

1 3 2

2 1 3

1 2 1

2 1 3

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 17

1 1 2

1 5 2

2 1 5

2 4 5

1 5 2

1 5 3

1 2 3

2 1 3

2 2 4

1 4 3

2 1 4

1 2 3

2 1 3

1 5 3

1 5 2

2 2 3

2 1 5

[出力例]

Yes

[入力例]

10 23

1 3 10

1 8 3

2 8 10

1 10 6

1 6 4

1 2 4

1 1 9

1 7 9

1 7 2

2 8 1

2 6 5

2 10 9

1 5 6

1 6 4

1 7 10

1 3 10

2 8 2

2 1 5

2 2 10

1 7 2

2 2 10

1 7 6

2 7 5

[出力例]

Yes

■参照サイト
第九回アルゴリズム実技検定

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題G (連結) を解いてみた.

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題G (連結) を解いてみた.

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