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

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

■感想.
1. 方針を絞り込めたので, AC版に到達できたと思う.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 個人的には, AtCoder Beginner Contest 157 の D – Friend Suggestionsに, どことなく似ている問題に思えた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 177 解説をご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#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 connection[202020]; // 連結成分番号を保存.
int appearance[202020]; // 連結成分番号の出現回数.

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

int main() {
    
    // 1. 入力情報取得.
    int N, M, a, b;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 探索を行い, 連結成分に分割.
    int idx = 0;
    rep(i, N) if(!connection[i]) bfs(G, i, ++idx);
    
    // 3. 各連結成分番号の出現回数を計算.
    rep(i, N) appearance[connection[i]]++;
    
    // 4. 連結成分の最大出現回数は？
    int ans = 0;
    repx(i, 1, idx + 1) ans = max(ans, appearance[i]);
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

#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 connection[202020]; // 連結成分番号を保存.

int appearance[202020]; // 連結成分番号の出現回数.

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

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

// ※bfsの動作確認用.

// @param G: グラフ.

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

// @param l: 連結成分番号(※1以上).

// @return: 特に無し.

void bfs(vvi &G, int s, int l){

// 1. 空のキュー.

queue<int> q;

// 2. 連結成分番号を設定.

connection[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

if(connection[e]) continue;

if(!connection[e] && e != s) connection[e] = l, q.push(e);

}

return;

}

int main() {

// 1. 入力情報取得.

int N, M, a, b;

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

vvi G(N);

rep(i, M){

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. 探索を行い, 連結成分に分割.

int idx = 0;

rep(i, N) if(!connection[i]) bfs(G, i, ++idx);

// 3. 各連結成分番号の出現回数を計算.

rep(i, N) appearance[connection[i]]++;

// 4. 連結成分の最大出現回数は？

int ans = 0;

repx(i, 1, idx + 1) ans = max(ans, appearance[i]);

// 5. 出力.

printf("%d\n", ans);

return 0;

}

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

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

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

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

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

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

[入力例]
5 0

[出力例]
1

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

[出力例]
3

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

[出力例]
2

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

[出力例]
3

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

[出力例]
5

100

101

102

103

104

105

106

107

[入力例]

5 3

1 2

3 4

5 1

[出力例]

※AtCoderテストケースより

[入力例]

4 10

1 2

2 1

1 2

2 1

1 2

1 3

1 4

2 3

2 4

3 4

[出力例]

※AtCoderテストケースより

[入力例]

10 4

3 1

4 1

5 9

2 6

[出力例]

※AtCoderテストケースより

[入力例]

5 0

[出力例]

[入力例]

9 9

1 2

2 3

3 1

4 5

5 6

6 4

7 8

8 9

9 7

[出力例]

[入力例]

5 4

1 2

2 1

3 4

4 3

[出力例]

[入力例]

11 10

1 2

2 1

3 4

4 3

5 6

6 5

7 8

8 7

9 10

10 11

[出力例]

[入力例]

15 17

1 2

1 15

3 4

4 5

5 3

6 7

7 8

8 9

9 6

9 7

10 11

11 12

12 10

12 13

13 10

13 14

14 10

[出力例]

■参照サイト
AtCoder Beginner Contest 177

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

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

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

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