[AtCoder] ABC 146 D – Coloring Edges on Tree
問題
方針
必要な色の数は、頂点の最大次数となるので、任意の頂点から幅優先探索を行い、色を振り分けていきます。辺の色を順番に出力する必要があるので、マップを使って管理します。また、色を分けるときに使用できない色を管理するためにセットを使います。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N; cin >> N; int a[N- 1], b[N - 1]; vector<int> adj[N]; int d[N]{}; for (int i = 0; i < N - 1; i++) { cin >> a[i] >> b[i]; a[i]--; b[i]--; d[a[i]]++; d[b[i]]++; adj[a[i]].push_back(b[i]); adj[b[i]].push_back(a[i]); } int l = 0; for (int i : d) { l = max(l, i); } int c[N]; fill(c, c + N, -1); deque<int> q; q.push_back(0); int vis[N]{}; vis[0] = 1; map<int, int> m[N]; set<int> s[N]; map<string, int> t; while (!q.empty()) { int u = q.front(); q.pop_front(); int k = 1; for (int j = 0; j < adj[u].size(); j++) { int v = adj[u][j]; if (m[u].count(v) == 0 && m[v].count(u) == 0) { while (s[u].count(k) != 0 || s[v].count(k) != 0) { k++; } m[u][v] = k; m[v][u] = k; s[u].insert(k); s[v].insert(k); } if (vis[v] == 0) { vis[v] = 1; q.push_back(v); } } } cout << l << "\n"; for (int i = 0; i < N - 1; i++) { cout << m[a[i]][b[i]] << "\n"; } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません