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

C++の練習を兼ねて, AtCoder Beginner Contest 266 の問題F (Well-defined Path Queries on a Namori) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, なもりグラフの性質を学習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc266/editorial/4698
// 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
set<int> C[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N){
        int u, v;
        scanf("%d %d", &u, &v);
        --u;
        --v;
        
        // 通常のグラフ.
        G[u].pb(v);
        G[v].pb(u);
        
        // 閉路検出用.
        C[u].insert(v);
        C[v].insert(u);
    }
    
    // 2. 閉路検出.
    queue<int> q;
    rep(i, N) if(C[i].size() == 1) q.push(i);
    while(!q.empty()){
        // キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 取り出した要素を処理.
        for(auto &v : C[u]){
            // 辺(v, u) を 削除.
            C[v].erase(u);
            
            // 保存.
            if(C[v].size() == 1) q.push(v);
        }
        
        // 辺(u, v) を 削除.
        C[u].clear();
    }
    
    // 3. 閉路を構成する頂点.
    set<int> st;
    rep(i, N) if(C[i].size()) st.insert(i);
    
    // 4. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!c[e] && e != s && !st.count(e)) c[e] = l, q.push(e);
        }
    };
    
    // 5. グループ分け.
    int c[N], idx = 0;
    rep(i, N) c[i] = 0;
    rep(i, N) if(st.count(i) && !c[i]) bfs(G, i, c, ++idx);
    
    // 6. クエリ回答.
    int Q;
    scanf("%d", &Q);
    rep(i, Q){
        // 6-1. クエリ入力情報.
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        
        // 6-2. 頂点 x, y が, ともに閉路上にある.
        if(st.count(x) && st.count(y)){
            puts("No");
            continue;
        }
        
        // 6-3. 上記以外.
        printf("%s\n", (c[x] == c[y]) ? "Yes" : "No");
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

// 解き直し.

// https://atcoder.jp/contests/abc266/editorial/4698

// 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

set<int> C[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N){

int u, v;

scanf("%d %d", &u, &v);

--u;

--v;

// 通常のグラフ.

G[u].pb(v);

G[v].pb(u);

// 閉路検出用.

C[u].insert(v);

C[v].insert(u);

}

// 2. 閉路検出.

queue<int> q;

rep(i, N) if(C[i].size() == 1) q.push(i);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

C[v].erase(u);

// 保存.

if(C[v].size() == 1) q.push(v);

}

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

C[u].clear();

}

// 3. 閉路を構成する頂点.

set<int> st;

rep(i, N) if(C[i].size()) st.insert(i);

// 4. bfs.

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

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

// 空のキュー.

queue<int> q;

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

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &e : G[u]) if(!c[e] && e != s && !st.count(e)) c[e] = l, q.push(e);

}

};

// 5. グループ分け.

int c[N], idx = 0;

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

rep(i, N) if(st.count(i) && !c[i]) bfs(G, i, c, ++idx);

// 6. クエリ回答.

int Q;

scanf("%d", &Q);

rep(i, Q){

// 6-1. クエリ入力情報.

int x, y;

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

--x;

--y;

// 6-2. 頂点 x, y が, ともに閉路上にある.

if(st.count(x) && st.count(y)){

puts("No");

continue;

}

// 6-3. 上記以外.

printf("%s\n", (c[x] == c[y]) ? "Yes" : "No");

}

return 0;

}

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

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

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

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

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

[出力例]
No
No
No

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

[出力例]
No
No
Yes

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

[出力例]
No
Yes
Yes
Yes
No
Yes
No
No
Yes
No

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

[入力例]

1 2

2 3

1 3

1 4

2 5

1 2

1 4

1 5

[出力例]

Yes

※AtCoderテストケースより

[入力例]

3 5

5 7

4 8

2 9

1 2

7 9

1 6

4 10

2 5

2 10

1 8

6 9

8 10

6 8

3 10

3 9

1 10

5 8

1 10

7 8

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1 2

1 3

2 3

1 2

1 3

2 3

[出力例]

[入力例]

1 2

1 3

2 3

3 4

1 2

2 4

3 4

[出力例]

Yes

[入力例]

1 5

1 6

1 13

2 3

2 4

2 20

5 7

5 20

6 10

6 17

7 8

7 16

9 10

9 11

9 12

10 20

13 14

13 15

17 18

17 19

1 5

1 15

1 14

6 17

6 10

3 20

5 10

7 11

6 18

1 20

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 266

C++の練習を兼ねて, AtCoder Beginner Contest 266 の 問題F (Well-defined Path Queries on a Namori) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 266 の問題F (Well-defined Path Queries on a Namori) を解いてみた.

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