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

C++の練習を兼ねて, AtCoder Beginner Contest 291 の問題E (Find Permutation) を解いてみた.

■感想.
1. 問題Eは, 方針を絞り込むことが出来たので, AC版に到達できたと思う.
2. 個人的には, 有向グラフの性質を確認できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 291 解説の各リンクをご覧下さい.

■C++版プログラム(問題E／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 iDegree[202020], oDegree[202020], ans[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        
        // 有向グラフ.
        G[y].pb(x);
        
        // 頂点次数.
        ++oDegree[x];
        ++iDegree[y];
    }
    
    // 2. 初期化.
    // -> 出次数ゼロの頂点.
    queue<int> q;
    rep(i, N) if(!oDegree[i]) q.push(i);
    
    // 3. 数列 A の 構築.
    bool ok = true;
    int n = N + 1;
    while(!q.empty()){
        // 一意に特定できない(サイズが, 2以上).
        if(q.size() >= 2){
            ok = false;
            break;
        }
        
        // キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 数列 A.
        ans[u] = --n;
        
        // 隣接頂点.
        for(auto &v : G[u]){
            // 辺(v, u) を 削除.
            --iDegree[u];
            --oDegree[v];
            
            // 出次数ゼロの頂点.
            if(!oDegree[v]) q.push(v);
        }
    }
    
    // 4. 例外.
    if(!ok || n > 1){
        puts("No");
        return 0;
    }
    
    // 5. 上記以外.
    puts("Yes");
    rep(i, N) printf("%d%s", ans[i], (i < N - 1) ? " " : "\n");
    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 iDegree[202020], oDegree[202020], ans[202020];

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

rep(i, M){

int x, y;

scanf("%d %d", &x, &y);

--x;

--y;

// 有向グラフ.

G[y].pb(x);

// 頂点次数.

++oDegree[x];

++iDegree[y];

}

// 2. 初期化.

// -> 出次数ゼロの頂点.

queue<int> q;

rep(i, N) if(!oDegree[i]) q.push(i);

// 3. 数列 A の構築.

bool ok = true;

int n = N + 1;

while(!q.empty()){

// 一意に特定できない(サイズが, 2以上).

if(q.size() >= 2){

ok = false;

break;

}

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

int u = q.front();

q.pop();

// 数列 A.

ans[u] = --n;

// 隣接頂点.

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

// 辺(v, u) を削除.

--iDegree[u];

--oDegree[v];

// 出次数ゼロの頂点.

if(!oDegree[v]) q.push(v);

}

// 4. 例外.

if(!ok || n > 1){

puts("No");

return 0;

}

// 5. 上記以外.

puts("Yes");

rep(i, N) printf("%d%s", ans[i], (i < N - 1) ? " " : "\n");

return 0;

}

[入力例]
3 2
3 1
2 3

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

[入力例]
3 2
3 1
3 2

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

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

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

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

[出力例]
No

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

[出力例]
No

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

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

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

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

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

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

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

[入力例]

3 2

3 1

2 3

[出力例]

Yes

3 1 2

※AtCoderテストケースより

[入力例]

3 2

3 1

3 2

[出力例]

※AtCoderテストケースより

[入力例]

4 6

1 2

2 3

3 4

[出力例]

Yes

1 2 3 4

※AtCoderテストケースより

[入力例]

4 4

1 2

2 4

1 3

3 4

[出力例]

[入力例]

5 5

4 3

3 2

4 5

5 1

1 2

[出力例]

[入力例]

10 15

1 2

2 3

2 4

3 4

4 10

4 5

5 6

5 8

6 8

6 7

7 8

7 9

8 9

8 10

9 10

[出力例]

Yes

1 2 3 4 5 6 7 8 9 10

[入力例]

12 18

12 11

12 9

11 9

11 10

10 9

9 7

10 7

7 6

7 8

8 6

6 5

5 2

5 3

2 3

2 1

3 1

3 4

4 1

[出力例]

Yes

12 9 10 11 8 7 5 6 4 3 2 1

[入力例]

15 21

15 14

15 10

14 10

10 9

10 8

9 8

8 2

2 1

8 1

1 7

8 7

7 3

1 3

3 4

4 5

4 6

6 5

5 11

11 13

11 12

13 12

[出力例]

Yes

7 6 9 10 12 11 8 5 4 3 13 15 14 2 1

■参照サイト
AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS）

C++の練習を兼ねて, AtCoder Beginner Contest 291 の 問題E (Find Permutation) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 291 の問題E (Find Permutation) を解いてみた.

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