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

C++の練習を兼ねて, AtCoder Regular Contest 022 の問題C (C – ロミオとジュリエット) を解いてみた.

■感想.
1. 木の直径を求める方針で実装したところ, AC版となった.
2. 幅優先探索(BFS) を復習出来たので, 良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトARC 022 解説をご覧下さい.

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

#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 pb push_back
int d0[101010], df[101010]; // 距離を保存

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @param d: 探索開始地点からの距離.
// @return: 特に無し.
void bfs(vvi &G, int s, int* d){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    d[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        
        // 4. キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            if(d[e] > 0)            continue;
            if(d[e] == 0 && e != s) d[e] = d[u] + 1, q.push(e);
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 頂点 1 から 各頂点までの距離を計算.
    bfs(G, 0, d0);
    
    // 3. 頂点 1 から, もっとも遠い頂点 f を, 1つ取得.
    int maxD = 0;
    int f = -1;
    rep(i, N) maxD = max(maxD, d0[i]);
    rep(i, N){
        if(d0[i] == maxD){
            f = i;
            break;
        }
    }
    
    // 4. 頂点 f から, 各頂点までの距離を計算.
    bfs(G, f, df);
    // rep(i, N) printf("%d ", df[i]);
    // puts("");
    
    // 5. 頂点 f から, もっとも遠い頂点 g を, 1つ取得.
    maxD = 0;
    int g = -1;
    rep(i, N) maxD = max(maxD, df[i]);
    rep(i, N){
        if(df[i] == maxD){
            g = i;
            break;
        }
    }
    
    // 6. 出力.
    assert(f != -1 && g != -1);
    printf("%d %d\n", f + 1, g + 1);
    return 0;
    
}

#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 pb push_back

int d0[101010], df[101010]; // 距離を保存

// グラフを幅優先探索する.

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

// ※bfsの動作確認用.

// @param G: グラフ.

// @param s: グラフの探索開始頂点.

// @param d: 探索開始地点からの距離.

// @return: 特に無し.

void bfs(vvi &G, int s, int* d){

// 1. 空のキュー.

queue<int> q;

// 2. 訪問済みフラグ設定.

// ※スタート地点は, 距離ゼロを指定.

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

if(d[e] > 0) continue;

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

}

return;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

int a, b;

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

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

bfs(G, 0, d0);

// 3. 頂点 1 から, もっとも遠い頂点 f を, 1つ取得.

int maxD = 0;

int f = -1;

rep(i, N) maxD = max(maxD, d0[i]);

rep(i, N){

if(d0[i] == maxD){

f = i;

break;

}

// 4. 頂点 f から, 各頂点までの距離を計算.

bfs(G, f, df);

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

// puts("");

// 5. 頂点 f から, もっとも遠い頂点 g を, 1つ取得.

maxD = 0;

int g = -1;

rep(i, N) maxD = max(maxD, df[i]);

rep(i, N){

if(df[i] == maxD){

g = i;

break;

}

// 6. 出力.

assert(f != -1 && g != -1);

printf("%d %d\n", f + 1, g + 1);

return 0;

}

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

[出力例]
5 10
※AtCoderのテストケースより

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

[出力例]
4 3
※AtCoderのテストケースより

但し, 上記のプログラムでは, 以下の内容が出力される.
2 3

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

[出力例]
19 13

[入力例]

7 6

3 2

2 4

4 5

8 9

1 8

1 6

1 2

9 10

[出力例]

5 10

※AtCoderのテストケースより

[入力例]

1 2

1 3

1 4

[出力例]

4 3

※AtCoderのテストケースより

但し, 上記のプログラムでは, 以下の内容が出力される.

2 3

[入力例]

13 7

7 4

4 2

6 2

11 6

18 10

10 3

19 15

15 10

20 17

17 5

12 5

5 3

3 2

14 8

8 2

16 9

9 1

2 1

[出力例]

19 13

■参照サイト
AtCoder Regular Contest 022

C++の練習を兼ねて, AtCoder Regular Contest 022 の 問題C (C – ロミオとジュリエット) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 022 の問題C (C – ロミオとジュリエット) を解いてみた.

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