C++ の動作確認をしてみた（５１３）

C++の練習を兼ねて, 競プロ典型 90 問の問題054 (Takahashi Number) を解いてみた.

■感想.
1. 問題054は, 方針が見えなかったので, (問題054 (Takahashi Number) 解説) を参考に実装したところ, AC版に到達出来た.
2. 幅優先探索(応用版, グラフの辺数削減)の復習が出来たので, 非常に良かったと思う..
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題054 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/054.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<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 pb push_back

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N + M);
    rep(i, M){
        int k;
        scanf("%d", &k);
        
        // 新たに追加する頂点.
        int u = N + i;
        
        // グラフ作成.
        rep(j, k){
            int v;
            scanf("%d", &v);
            v--;
            G[u].pb(v);
            G[v].pb(u);
        }
    }
    
    // 2. 頂点 1 から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. スタート地点(距離 0)を設定.
        d[s] = 0;
        
        // 2-3. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-4. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-5. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 2-5. 未訪問の頂点を処理.
                if((d[e] == -1) && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    int d[N + M];
    rep(i, N + M) d[i] = -1;
    bfs(G, 0, d);
    // rep(i, N + M) printf("%d ", d[i]);
    // puts("");
    
    // 3. 出力.
    rep(i, N) printf("%d\n", (d[i] != -1) ? (d[i] / 2) : -1);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/054.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vvi = vector<vector<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 pb push_back

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N + M);

rep(i, M){

int k;

scanf("%d", &k);

// 新たに追加する頂点.

int u = N + i;

// グラフ作成.

rep(j, k){

int v;

scanf("%d", &v);

v--;

G[u].pb(v);

G[v].pb(u);

}

// 2. 頂点 1 から各頂点までの距離を計算.

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

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

// 2-1. 空のキュー.

queue<int> q;

// 2-2. スタート地点(距離 0)を設定.

d[s] = 0;

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

q.push(s);

while(!q.empty()){

// 2-4. キューから取り出す.

int u = q.front();

q.pop();

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

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

// 2-5. 未訪問の頂点を処理.

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

}

return;

};

int d[N + M];

rep(i, N + M) d[i] = -1;

bfs(G, 0, d);

// rep(i, N + M) printf("%d ", d[i]);

// puts("");

// 3. 出力.

rep(i, N) printf("%d\n", (d[i] != -1) ? (d[i] / 2) : -1);

return 0;

}

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

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

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

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

[入力例]
4 1
3
2 3 4

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

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

[出力例]
0
2
1
2
2
2
2
1
3
2
-1
※AtCoderテストケースより

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

[出力例]
0
1
1
1
1
2
2

[入力例]
25 13
5
1 2 3 4 5
2
2 17
4
17 18 19 20
2
3 6
2
6 10
2
6 7
3
7 8 9
2
5 11
2
11 12
2
11 13
4
13 14 15 16
2
8 21
5
21 22 23 24 25

[出力例]
0
1
1
1
1
2
3
4
4
3
2
3
3
4
4
4
2
3
3
3
5
6
6
6
6

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

[入力例]

6 3

1 2 3

3 4

5 6

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 3

1 2

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

4 1

2 3 4

[出力例]

-1

※AtCoderテストケースより

[入力例]

11 5

2 6 9 10

1 3 8

2 4 6 8 10

6 7

5 6 7 8

[出力例]

-1

※AtCoderテストケースより

[入力例]

7 3

1 2 3 4

1 5

5 6 7

[出力例]

[入力例]

25 13

1 2 3 4 5

2 17

17 18 19 20

3 6

6 10

6 7

7 8 9

5 11

11 12

11 13

13 14 15 16

8 21

21 22 23 24 25

[出力例]

■参照サイト
054 – Takahashi Number
問題054 (Takahashi Number) 解説

C++の練習を兼ねて, 競プロ典型 90 問 の 問題054 (Takahashi Number) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問の問題054 (Takahashi Number) を解いてみた.

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