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

C++の練習を兼ねて, AtCoder Beginner Contest 146 の問題D (D – Coloring Edges on Tree) を解いてみた.

■感想.
1. 非常に苦労したものの, 解説見る前に, AC版となったので良かったと思う.
2. 但し, スリムな実装方法が思いつかなかったので, 上級者の方々のソースを見て, 勉強する必要があると感じた.

本家のサイトABC 146解説をご覧下さい.

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

// TODO: 計算量が非常に多い気がする.
#include <bits/stdc++.h>
using namespace std;
#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 pb push_back
#define a first
#define b second
const int MAX = 101010;
int memo[MAX];
vector<int> graph[MAX];
map<pair<int, int>, int> m; // 着色時の頂点ペア, 色を保存.
vector<pair<int, int>> o;   // 入力時の頂点ペアを保存.
set<int> color[MAX];
int maxColor;

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param s: 探索開始の頂点番号.
// @return: 特に無し.
void bfs(int s){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    memo[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    
    // 4. キュー q が 空になるまで, 探索.
    while(!q.empty()){
        
        // 5. 頂点 u を キュー q から取り出す.
        int u = q.front();
        q.pop();
        
        // 6. 取り出した要素を処理.
        int c = 1;
        for(auto &e : graph[u]){
            // 6-1. 頂点u の 隣接する頂点e が, 未訪問だったら, キュー q に追加.
            if(memo[e] == 0 && e != s){
                // 頂点e を キュー q に追加.
                q.push(e);
                // 頂点e に 距離memo[u] プラス 1 を 加算.
                memo[e] += (memo[u] + 1);
                // 色を着色.
                // すでに使用している色があれば, Skip.
                while(color[u].count(c) != 0) c++;
                color[u].insert(c);
                color[e].insert(c);
                m[{u, e}] = c;
                m[{e, u}] = c;
                // 必要とする色の最大数を更新.
                maxColor = max(maxColor, c);
            }
        }
    }
}

int main(){
    
    // 1. 入力情報.
    int N, a, b;
    scanf("%d", &N);
    
    // 2. グラフ作成.
    rep(i, N - 1){
        scanf("%d %d", &a, &b);
        a--, b--;
        graph[a].pb(b);
        graph[b].pb(a);
        o.pb({a, b}); // オリジナルの入力情報.
    }
    
    // 3. 頂点 0 から 探索.
    bfs(0);
    // rep(i, N) printf("%d ", memo[i]);
    // printf("\n");
    // printf("maxColor=%d\n", maxColor);
    // for(auto &p : m) printf("a=%d b=%d c=%d\n", p.a.a, p.a.b, p.b);
    
    // 4. 出力.
    printf("%d\n", maxColor);
    for(auto &p : o) printf("%d\n", m[p]);
    return 0;

}

// TODO: 計算量が非常に多い気がする.

#include <bits/stdc++.h>

using namespace std;

#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 pb push_back

#define a first

#define b second

const int MAX = 101010;

int memo[MAX];

vector<int> graph[MAX];

map<pair<int, int>, int> m; // 着色時の頂点ペア, 色を保存.

vector<pair<int, int>> o; // 入力時の頂点ペアを保存.

set<int> color[MAX];

int maxColor;

// グラフを幅優先探索する.

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

// ※bfsの動作確認用.

// @param s: 探索開始の頂点番号.

// @return: 特に無し.

void bfs(int s){

// 1. 空のキュー.

queue<int> q;

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

// ※スタート地点は, 距離ゼロを指定.

memo[s] = 0;

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

q.push(s);

// 4. キュー q が空になるまで, 探索.

while(!q.empty()){

// 5. 頂点 u をキュー q から取り出す.

int u = q.front();

q.pop();

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

int c = 1;

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

// 6-1. 頂点u の隣接する頂点e が, 未訪問だったら, キュー q に追加.

if(memo[e] == 0 && e != s){

// 頂点e をキュー q に追加.

q.push(e);

// 頂点e に距離memo[u] プラス 1 を加算.

memo[e] += (memo[u] + 1);

// 色を着色.

// すでに使用している色があれば, Skip.

while(color[u].count(c) != 0) c++;

color[u].insert(c);

color[e].insert(c);

m[{u, e}] = c;

m[{e, u}] = c;

// 必要とする色の最大数を更新.

maxColor = max(maxColor, c);

}

int main(){

// 1. 入力情報.

int N, a, b;

scanf("%d", &N);

// 2. グラフ作成.

rep(i, N - 1){

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

a--, b--;

graph[a].pb(b);

graph[b].pb(a);

o.pb({a, b}); // オリジナルの入力情報.

}

// 3. 頂点 0 から探索.

bfs(0);

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

// printf("\n");

// printf("maxColor=%d\n", maxColor);

// for(auto &p : m) printf("a=%d b=%d c=%d\n", p.a.a, p.a.b, p.b);

// 4. 出力.

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

for(auto &p : o) printf("%d\n", m[p]);

return 0;

}

[入力例]
3
1 2
2 3

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

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

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

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

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

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

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

[入力例]
30
1 18
1 19
1 20
2 4
10 28
10 29
3 8
3 9
4 10
4 27
5 11
5 12
2 5
2 6
3 7
5 13
7 17
8 14
8 15
10 23
10 24
1 2
1 3
10 25
10 26
6 30
7 16
19 21
19 22

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

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

[入力例]

1 2

2 3

[出力例]

※AtCoderテストケースより

[入力例]

1 2

2 3

2 4

2 5

4 7

5 6

6 8

[出力例]

※AtCoderテストケースより

[入力例]

1 2

1 3

1 4

1 5

1 6

[出力例]

※AtCoderテストケースより

[入力例]

1 2

2 3

3 4

4 5

5 6

6 7

7 8

8 9

9 10

2 11

2 12

11 13

3 14

3 15

4 16

[出力例]

[入力例]

1 18

1 19

1 20

2 4

10 28

10 29

3 8

3 9

4 10

4 27

5 11

5 12

2 5

2 6

3 7

5 13

7 17

8 14

8 15

10 23

10 24

1 2

1 3

10 25

10 26

6 30

7 16

19 21

19 22

[出力例]

■参照サイト
AtCoder Beginner Contest 146

C++の練習を兼ねて, AtCoder Beginner Contest 146 の 問題D (D – Coloring Edges on Tree) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 146 の問題D (D – Coloring Edges on Tree) を解いてみた.

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