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

C++の練習を兼ねて, 競プロ典型 90 問の問題021 (Come Back in One Piece) を解いてみた.

■感想.
1. 実装方針を決めることができたこと, および, 過去問の実装を参照できたので, AC版に到達出来たと思う.
2. 強連結成分分解(Strongly Connected Component)について, 理解を深めることが出来たので, 非常に良かったと思う.
3. 問題021は, 過去問 AtCoder Beginner Contest 202 (E – Count Descendants) を一部拝借する形で, 実装に反映した.
4. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int, int>;
using PQ = priority_queue<P>;
#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 a first
#define b second
#define pb push_back
int memo[101010], t[101010], scc[101010];
LL gCount[101010];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G1(N), G2(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G1[a].pb(b); // 有向辺.
        G2[b].pb(a); // 有向辺(逆向き).
    }
    
    // 強連結成分分解(Strongly Connected Component).
    // https://manabitimes.jp/math/1250
    // 2. 行き止まりの順番を保存.
    int idx = 0;
    PQ pq;
    auto dfs1 = [&](auto&& self, int c) -> void{
        // 訪問済フラグ設定.
        memo[c] = 1;
        
        // 取り出した要素を処理.
        for(auto &n : G1[c]) if(!memo[n]) self(self, n);
        
        // 行き止まりの順番を保存.
        pq.push({++idx, c});
    };
    rep(i, N) if(!memo[i]) dfs1(dfs1, i);
    
    // 3. 強連結成分に分解.
    idx = 0;
    auto dfs2 = [&](auto&& self, int c) -> void{
        // 連結成分番号設定.
        scc[c] = idx;
        
        // 取り出した要素を処理.
        for(auto &n : G2[c]) if(!scc[n]) self(self, n);
    };
    while(!pq.empty()){
        // 要素を取り出す.
        P p = pq.top();
        pq.pop();
        
        // 連結成分番号が設定済み.
        if(scc[p.b]) continue;
        
        // インクリメント.
        idx++;
        
        // 連結成分番号設定.
        dfs2(dfs2, p.b);
    }
    
    // 4. 各強連結成分の大きさを保存.
    rep(i, N) gCount[scc[i]]++;
    
    // 5. 集計.
    LL ans = 0;
    repx(i, 1, idx + 1) ans += gCount[i] * (gCount[i] - 1) / 2;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

using PQ = priority_queue<P>;

#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 a first

#define b second

#define pb push_back

int memo[101010], t[101010], scc[101010];

LL gCount[101010];

int main(){

// 1. 入力情報.

int N, M;

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

vvi G1(N), G2(N);

rep(i, M){

int a, b;

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

a--, b--;

G1[a].pb(b); // 有向辺.

G2[b].pb(a); // 有向辺(逆向き).

}

// 強連結成分分解(Strongly Connected Component).

// https://manabitimes.jp/math/1250

// 2. 行き止まりの順番を保存.

int idx = 0;

PQ pq;

auto dfs1 = [&](auto&& self, int c) -> void{

// 訪問済フラグ設定.

memo[c] = 1;

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

for(auto &n : G1[c]) if(!memo[n]) self(self, n);

// 行き止まりの順番を保存.

pq.push({++idx, c});

};

rep(i, N) if(!memo[i]) dfs1(dfs1, i);

// 3. 強連結成分に分解.

idx = 0;

auto dfs2 = [&](auto&& self, int c) -> void{

// 連結成分番号設定.

scc[c] = idx;

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

for(auto &n : G2[c]) if(!scc[n]) self(self, n);

};

while(!pq.empty()){

// 要素を取り出す.

P p = pq.top();

pq.pop();

// 連結成分番号が設定済み.

if(scc[p.b]) continue;

// インクリメント.

idx++;

// 連結成分番号設定.

dfs2(dfs2, p.b);

}

// 4. 各強連結成分の大きさを保存.

rep(i, N) gCount[scc[i]]++;

// 5. 集計.

LL ans = 0;

repx(i, 1, idx + 1) ans += gCount[i] * (gCount[i] - 1) / 2;

// 6. 出力.

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

return 0;

}

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

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

[入力例]
100 1
1 2

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

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

[出力例]
4

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

[出力例]
20

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

[出力例]
13

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

[出力例]
51

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

[入力例]

4 7

1 2

2 1

2 3

4 3

4 1

1 4

2 3

[出力例]

※AtCoderテストケースより

[入力例]

100 1

1 2

[出力例]

※AtCoderテストケースより

[入力例]

9 11

1 2

2 1

2 9

2 3

3 6

6 7

7 8

8 6

3 4

4 5

3 5

[出力例]

[入力例]

12 18

1 2

2 1

5 1

2 3

4 2

3 8

3 4

4 6

4 7

4 5

8 11

11 12

12 8

8 9

9 10

10 8

[出力例]

[入力例]

17 21

1 2

2 3

4 1

4 3

8 4

3 8

10 8

10 11

11 12

8 12

9 12

7 9

9 13

5 7

6 5

7 6

14 13

16 14

16 15

15 13

17 13

[出力例]

[入力例]

23 38

1 3

3 1

3 2

2 4

3 16

16 17

17 18

18 17

3 18

4 6

6 4

1 5

5 1

5 6

5 19

20 5

19 20

19 21

21 22

22 23

23 22

23 19

6 7

7 9

8 7

8 9

9 10

10 11

11 9

11 15

15 11

10 12

12 10

12 13

13 14

14 13

14 15

[出力例]

■参照サイト
021 – Come Back in One Piece
強連結成分分解の意味とアルゴリズム

C++の練習を兼ねて, 競プロ典型 90 問 の 問題021 (Come Back in One Piece) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問の問題021 (Come Back in One Piece) を解いてみた.

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