LoginSignup
2
1

強連結成分(SCC)を使えばループ(閉路)を繰り返す系の問題がかなり簡潔に記述できる

Last updated at Posted at 2022-03-28

前提:記事中におけるグラフは、次の頂点 = f(現在の頂点) の形でグラフが定義される、いわゆる functional graph と呼ばれるものを想定しています。

大量のシミュレーションが必要で、愚直に実装すると TLE するけど、実はある部分はループ(閉路)を繰り返すだけで本当にシミュレーションが必要な部分は少ないという問題は時々出ます。

D - Teleporter

 これを解くには、

  • 閉路検出を実装する
  • ダブリングを用いる

 という方法がありますが、前者は手動で実装するには結構重いです。けんちょんさんの解説がわかりやすいのでソースコードをそのまま写させていただきますが、

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; 
    long long K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i], --A[i];

    deque<int> a; // 繰り返しの部分
    vector<bool> seen(N, false); // 一度見たかどうか
    int cur = 0;
    while (true) {
        // 一度通った頂点を見つけたときの処理
        if (seen[cur]) {
            while (a[0] != cur) {
                // 最初の余計な数手分を除去する
                --K;
                a.pop_front();

                // 繰り返す前に K が限界になったらリターン
                if (K == 0) {
                    cout << a[0]+1 << endl;
                    return 0;
                }
            }
            break;
        }
        // 最初は愚直にシミュレーションしつつ、履歴をメモしていく
        a.push_back(cur);
        seen[cur] = true;
        cur = A[cur];
    }
    cout << a[K % a.size()]+1 << endl;
}

 メモ用の配列を別に用意したり、「最初の余計な数手分を除去する」「Kが限界になったらリターン」等の条件分岐が複雑です。本番でこういうのを一発で AC できる自身がない……。もっと逐次的に処理できないものか。

強連結成分

 という訳で、強連結成分を検出するアルゴリズムである SCC を使ってこの問題を解いていきます。これを使うと、functional graph においては、ループ(閉路)を検出することができます。

 なので、愚直なシミュレーションをほぼ流用する形で、

  1. 愚直なシミュレーションを続ける
  2. ループにたどり着いた段階で、残りのシミュレーション回数のうちループする分を一括処理する
  3. 愚直なシミュレーションを続ける

 という逐次的な処理にできます。step2 が問題の本質ですね。

 つまり、最終的には、その場所がループ上であるかを判別する(そうでない場合はループの長さを返す)ような配列 loop があるとして、

    int pos = 0;
    while (k--)
    {
        pos = a[pos];
        if (loop[pos] > -1)
        {
            k %= loop[pos];
        }
    }
    cout << pos + 1 << endl;

 という形に持っていきたいです。こうすれば、kの場合分けなどを一切考えずに一括処理できます。

 そのようなloopを用意するために、SCC を用いて以下のような下処理を行います。

    ll n, k;
    cin >> n >> k;
    scc_graph graph(n); // SCCグラフの構造体
    vector<int> a(n);
    vector<ll> loop(n, -1); // ループの判別配列
    rep(i, n)
    {
        cin >> a[i];
        a[i]--;
        graph.add_edge(i, a[i]);
        if (i == a[i])
        {
            loop[i] = 1; // 自己ループの場合は個別処理
        }
    }
    vector<vector<int>> scc = graph.scc();
    for (auto v : scc)
    {
        if (v.size() == 1)
        {
            continue; // 強連結成分が 1 個の時は自己ループまたはループではない
        }
        for (int i : v)
        {
            loop[i] = v.size(); // 強連結成分が 2 個以上の時はループしている
        }
    }

ソースコード全体

#include <iostream>

using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i < n + 1; i++)
#define all(A) A.begin(), A.end()
#define itr(A, l, r) A.begin() + l, A.begin() + r
#define debug(var) cout << #var << " = " << var << endl;
typedef long long ll;

#include <atcoder/scc>
using namespace atcoder;

int main(void)
{
    ll n, k;
    cin >> n >> k;
    scc_graph graph(n);
    vector<int> a(n);
    vector<ll> loop(n, -1);
    rep(i, n)
    {
        cin >> a[i];
        a[i]--;
        graph.add_edge(i, a[i]);
        if (i == a[i])
        {
            loop[i] = 1;
        }
    }
    vector<vector<int>> scc = graph.scc();
    for (auto v : scc)
    {
        if (v.size() == 1)
        {
            continue;
        }
        for (int i : v)
        {
            loop[i] = v.size();
        }
    }
    int pos = 0;
    while (k--)
    {
        pos = a[pos];
        if (loop[pos] > -1)
        {
            k %= loop[pos];
        }
    }
    cout << pos + 1 << endl;
}

 注意点として、SCC は自己ループがあっても検出できないので、自己ループは個別に処理する必要があります。また、loop の初期値を 0 にすると、問題によっては 0 除算でエラーを起こす可能性があります(なので -1 にしています)。

もっと難しい問題

E - Putting Candies

 これはループを通る際に数値の加算があります。そのために配列を別に用意していますが、やることは基本的に同じです。

#include <iostream>

using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i < n + 1; i++)
#define all(A) A.begin(), A.end()
#define itr(A, l, r) A.begin() + l, A.begin() + r
#define debug(var) cout << #var << " = " << var << endl;
typedef long long ll;

#include <atcoder/scc>
using namespace atcoder;

int main(void)
{
    int n;
    ll k;
    cin >> n >> k;
    scc_graph graph(n);
    vector<int> a(n);
    vector<ll> loop(n, -1);
    vector<ll> loop_plus(n);
    rep(i, n)
    {
        int x;
        cin >> x;
        graph.add_edge(i, (i + x) % n);
        a[i] = x;
        if (i == (i + x) % n)
        {
            loop[i] = 1;
            loop_plus[i] = x;
        }
    }
    auto scc = graph.scc();
    for (auto v : scc)
    {
        if (v.size() == 1)
        {
            continue;
        }
        ll plus = 0;
        for (int i : v)
        {
            plus += a[i];
        }
        for (int i : v)
        {
            loop[i] = v.size();
            loop_plus[i] = plus;
        }
    }
    int pos = 0;
    ll ans = 0;
    while (k--)
    {
        ans += a[pos];
        pos = ans % n;
        if (loop[pos] > -1)
        {
            ans += loop_plus[pos] * (k / loop[pos]);
            k %= loop[pos];
        }
    }
    cout << ans << endl;
}

 

2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
1