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

C++の練習を兼ねて, 競プロ典型 90 問の問題062 (Paint All) を解いてみた.

■感想.
1. 問題062は, 方針が見えなかったので, (問題062 (Paint All) 解説) を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 逆順から考えるという視点が, 非常に面白い問題に感じた.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

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

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/062.jpg
// 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 main(){
    
    // 1. 入力情報.
    int N;
    vi x;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(i);
        G[b].pb(i);
        if((a == i) || (b == i)) x.pb(i);
    }
    
    // 2. 不可能な場合.
    if(x.size() == 0){
        puts("-1");
        return 0;
    }
    
    // 3. 指定した頂点から操作を進めていく.
    // https://ja.wikipedia.org/wiki/幅優先探索
    // -> 本問は, bfs に, 類似した実装で, 対応可能と見る.
    vi ans;
    auto bfs = [&](vvi &G, int s, int* d){
        // 3-1. 空のキュー.
        queue<int> q;
        
        // 3-2. 訪問済みフラグ設定.
        d[s] = 1;
        
        // 3-3. 探索地点 s をキュー q に追加.
        q.push(s);
        
        // 3-4. キューが空になるまで処理.
        while(!q.empty()){
            // 3-5. 頂点を取り出す.
            int u = q.front();
            q.pop();
            
            // 3-6. 操作の保存.
            ans.pb(u);
            
            // 3-7. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 3-8. 未訪問の頂点を処理.
                if(!d[e]) d[e] = 1, q.push(e);
            }
        }
        return;
    };
    int d[N];
    rep(i, N) d[i] = 0;
    for(auto &s : x) if(!d[s]) bfs(G, s, d);
    // rep(i, N) printf("%d ", d[i]);
    // puts("");
    
    // 4. 不可能な場合.
    if(ans.size() != N){
        puts("-1");
        return 0;
    }
    
    // 5. 出力.
    repr(i, N - 1, 0) printf("%d\n", ans[i] + 1);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/062.jpg

// 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 main(){

// 1. 入力情報.

int N;

vi x;

scanf("%d", &N);

vvi G(N);

rep(i, N){

int a, b;

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

a--, b--;

G[a].pb(i);

G[b].pb(i);

if((a == i) || (b == i)) x.pb(i);

}

// 2. 不可能な場合.

if(x.size() == 0){

puts("-1");

return 0;

}

// 3. 指定した頂点から操作を進めていく.

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

// -> 本問は, bfs に, 類似した実装で, 対応可能と見る.

vi ans;

auto bfs = [&](vvi &G, int s, int* d){

// 3-1. 空のキュー.

queue<int> q;

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

d[s] = 1;

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

q.push(s);

// 3-4. キューが空になるまで処理.

while(!q.empty()){

// 3-5. 頂点を取り出す.

int u = q.front();

q.pop();

// 3-6. 操作の保存.

ans.pb(u);

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

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

// 3-8. 未訪問の頂点を処理.

if(!d[e]) d[e] = 1, q.push(e);

}

return;

};

int d[N];

rep(i, N) d[i] = 0;

for(auto &s : x) if(!d[s]) bfs(G, s, d);

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

// puts("");

// 4. 不可能な場合.

if(ans.size() != N){

puts("-1");

return 0;

}

// 5. 出力.

repr(i, N - 1, 0) printf("%d\n", ans[i] + 1);

return 0;

}

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

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

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

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

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

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

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

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

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

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

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

[出力例]
5
4
2
1
3

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

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

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

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

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

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

[入力例]

3 4

1 3

2 3

2 1

[出力例]

※AtCoderテストケースより

[入力例]

1 1

2 2

3 3

[出力例]

※AtCoderテストケースより

[入力例]

3 4

4 5

1 1

5 1

3 2

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 5

2 4

6 6

5 2

1 3

4 1

[出力例]

※AtCoderテストケースより

[入力例]

5 1

3 9

7 8

9 3

3 7

10 10

3 5

4 7

1 1

6 6

[出力例]

-1

※AtCoderテストケースより

[入力例]

2 3

4 3

3 4

3 5

2 1

[出力例]

[入力例]

3 11

9 4

2 5

7 11

11 5

9 6

5 1

4 3

7 4

6 1

4 3

7 7

[出力例]

[入力例]

10 13

16 8

13 4

9 8

8 1

4 9

15 17

9 13

1 12

2 7

10 16

13 11

14 9

7 1

5 13

14 16

2 10

[出力例]

■参照サイト
062 – Paint All
問題062 (Paint All) 解説

C++の練習を兼ねて, 競プロ典型 90 問 の 問題062 (Paint All) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問の問題062 (Paint All) を解いてみた.

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