解説
操作を逆順に行うと、以下のように処理できます。
- について以下を行う。
- 頂点 から辺を 本以上たどって到達可能な頂点のうち、まだ以前の操作によって色が塗られていない頂点を色 で塗る。
- 操作によって色が塗られなかった頂点を色 で塗る。
各操作で頂点 から愚直にBFSやDFSを行って色を塗ると、計算量は になります。
ここで、ある頂点が以前の操作によって色が塗られている場合、その頂点から辺を 本以上たどって到達可能なすべての頂点も必ず以前の操作によって色が塗られているため、その頂点から先を探索する必要はありません。
よって、BFSやDFSを行うとき、すでに色が塗られた頂点で探索を打ち切ることで、各頂点から伸びる辺を調べる回数が高々 回になります。したがって、全体で で処理できます。
再帰関数を用いてDFSを行うとスタックオーバーフローが発生する可能性がありますが、ジャッジでは AC を得られました。
解答例 (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> to(n);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--; b--;
to[a].push_back(b);
}
int q;
cin >> q;
vector<int> x(q), y(q);
for (int i = 0; i < q; i++) {
cin >> x[i] >> y[i];
x[i]--;
}
vector<int> c(n);
for (int i = q-1; i >= 0; i--) {
if (c[x[i]] != 0) continue;
c[x[i]] = y[i];
queue<int> que;
que.push(x[i]);
while (que.size()) {
int v = que.front(); que.pop();
for (int u : to[v]) {
if (c[u] != 0) continue;
c[u] = y[i];
que.push(u);
}
}
}
for (int i = 0; i < n; i++) {
cout << c[i] << " \n"[i == n-1];
}
return 0;
}
解答例 (Python)
from collections import deque
n, m = map(int, input().split())
to = [[] for _ in range(n)]
for i in range(m):
a, b = map(int, input().split())
a, b = a-1, b-1
to[a].append(b)
q = int(input())
x, y = [0] * q, [0] * q
for i in range(q):
x[i], y[i] = map(int, input().split())
x[i] -= 1
c = [0] * n
for i in reversed(range(q)):
if c[x[i]] != 0: continue
c[x[i]] = y[i]
que = deque([x[i]])
while len(que):
v = que.popleft()
for u in to[v]:
if c[u] != 0: continue
c[u] = y[i]
que.append(u)
print(*c)
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。