[ABC245] F - Endless Walk
[Q] https://atcoder.jp/contests/abc245/tasks/abc245_f
1. グラフを張る。方向通りのGと、逆方向のHも用意。
2. 頂点0を出発。ひたすらGで行く。頂点通過ごとに、
turn = 歩数 と
seen = もう見たか
をメモする。
3. もしturn>0に戻ってきたならループ判定。
ループ地点から逆方向に進める場所全部が解答。ひたすらHを行く。頂点通過ごとに、
ans = 答え と
seen = もう見たか
をメモする。
Q. TLE沼
A.
こういう木があるとして
1
\
2
/ \
3 4
\ \
\ 5
\ /
6
\
7
1->2->4->5->6->7 と進んで、
2<-4<-5<-6<-7 と戻る。
2->3 と進むとき、
->6 は見ない。6以降にループがないことは、判明している。
実装
vector<ll> G[200020]; // 前方向
vector<ll> H[200020]; // 逆方向
ll turn[200020]; // 何ターン目に到着したか
bool seen[200020]; // もう見た
bool ans[200020]; // 無限に歩ける
ll N, M;
// 戻れるところ全部loop
void dfs_ok(ll u) {
// Hで戻れる場所を探索
for (auto h : H[u]) {
if (ans[h]) continue;
ans[h] = true;
seen[h] = true;
dfs_ok(h);
}
}
void dfs(ll u) {
// Gで進む場所を探索
for (auto g : G[u]) {
// 今探索で、同じ場所にきた
if (turn[g] > 0) {
ans[u] = true;
seen[u] = true;
// Hで行ける場所全部ansにする
dfs_ok(u);
}
// 次の手を見たことがあるなら、絶対ループはない。
if (seen[g]) continue;
seen[g] = true;
turn[g] = turn[u] + 1;
dfs(g);
}
// 歩数復元
turn[u] = 0;
}
int main() {
cincout();
cin >> N >> M;
rep(i, M) {
ll u, v;
cin >> u >> v;
--u, --v;
G[u].push_back(v);
H[v].push_back(u);
}
rep(i, N) {
if (seen[i]) continue;
turn[i] = 1;
dfs(i);
}
ll cnt = 0;
rep(i, N) cnt += ans[i];
cout << cnt << endl;
}
https://atcoder.jp/contests/abc245/submissions/30516553
この記事が気に入ったらサポートをしてみませんか?