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

C++の練習を兼ねて, AtCoder Library Practice Contest の問題G (SCC) を解いてみた.

■感想.
1. 問題Gは, 強連結成分分解を使う方針で, AC版に到達出来た.
2. 強連結成分分解(Strongly Connected Component)について, 改めて復習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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
const int MAX = 505050;
int memo[MAX], scc[MAX];

int main(){
    
    // 1. 入力情報.
    int N, M, a, b;
    scanf("%d %d", &N, &M);
    vvi G1(N), G2(N);
    rep(i, M){
        scanf("%d %d", &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. 強連結成分に分解.
    vvi ans(N + 1);
    idx = 0;
    auto dfs2 = [&](auto&& self, int c) -> void{
        // 連結成分番号設定.
        scc[c] = idx;
        
        // 取り出した要素を処理.
        for(auto &n : G2[c]) if(!scc[n]) self(self, n);
        
        // 頂点を保存(トポロジカルソート).
        ans[idx].pb(c);
    };
    while(!pq.empty()){
        // 要素を取り出す.
        P p = pq.top();
        pq.pop();
        
        // 連結成分番号が設定済み.
        if(scc[p.b]) continue;
        
        // インクリメント.
        idx++;
        
        // 連結成分番号設定.
        dfs2(dfs2, p.b);
    }
    
    // 4. 出力.
    printf("%d\n", idx);
    repx(i, 1, idx + 1){
        // 4-1. 強連結成分の頂点数.
        int l = ans[i].size();
        printf("%d ", l);
        
        // 4-2. 頂点を出力.
        rep(j, l){
            printf("%d", ans[i][j]);
            printf("%s", (j < l - 1) ? " " : "\n");
        }
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

const int MAX = 505050;

int memo[MAX], scc[MAX];

int main(){

// 1. 入力情報.

int N, M, a, b;

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

vvi G1(N), G2(N);

rep(i, M){

scanf("%d %d", &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. 強連結成分に分解.

vvi ans(N + 1);

idx = 0;

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

// 連結成分番号設定.

scc[c] = idx;

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

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

// 頂点を保存(トポロジカルソート).

ans[idx].pb(c);

};

while(!pq.empty()){

// 要素を取り出す.

P p = pq.top();

pq.pop();

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

if(scc[p.b]) continue;

// インクリメント.

idx++;

// 連結成分番号設定.

dfs2(dfs2, p.b);

}

// 4. 出力.

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

repx(i, 1, idx + 1){

// 4-1. 強連結成分の頂点数.

int l = ans[i].size();

printf("%d ", l);

// 4-2. 頂点を出力.

rep(j, l){

printf("%d", ans[i][j]);

printf("%s", (j < l - 1) ? " " : "\n");

}

return 0;

}

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

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

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

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

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

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

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

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

100

101

[入力例]

6 7

1 4

5 2

3 0

5 5

4 1

0 3

4 2

[出力例]

1 5

2 4 1

1 2

2 3 0

※AtCoderテストケースより

[入力例]

11 14

0 1

1 0

0 7

7 9

9 8

7 8

8 10

10 7

1 2

2 5

2 3

5 4

4 2

3 4

[出力例]

1 6

2 1 0

4 9 8 10 7

4 5 3 4 2

[入力例]

7 10

0 6

6 0

0 1

1 2

2 1

2 3

2 4

4 3

5 4

3 5

[出力例]

2 6 0

2 2 1

3 5 4 3

[入力例]

20 25

0 1

1 0

0 7

7 8

8 18

1 9

9 10

10 11

10 12

11 12

12 9

1 2

2 3

3 6

6 5

5 4

4 2

4 19

13 1

13 14

13 17

17 15

16 17

15 16

14 15

[出力例]

1 13

1 14

3 16 17 15

2 1 0

1 7

1 8

1 18

5 3 6 5 4 2

1 19

4 10 11 12 9

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

C++の練習を兼ねて, AtCoder Library Practice Contest の 問題G (SCC) を解いてみた.

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

C++の練習を兼ねて, AtCoder Library Practice Contest の問題G (SCC) を解いてみた.

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