[白俊]9466号*

9938 ワード
幅優先ナビゲーション BFS コーディングテスト コセット グラフ＃グラフ＃ Graph 白駿 テキストリンク
  • 周期の中で含まない元素の個数の
    • を求めます
  • の任意の要素から、サイクルに要素が含まれているかどうかを確認します->
    • を保存します.
    💻 C++ベース
    https://www.acmicpc.net/problem/9466
    ✔」アクセスした配列にbool値ではなくint値を入れると、文を繰り返すたびに初期化する必要がないため、時間的複雑度はO(N)となる.
    #include <cstdio>
#include <queue>
#include <utility>
#include <algorithm>

#define MAX 100001

using namespace std;

int choices[MAX];
int visited[MAX];

void search(int n, int start)
{
    int cur = start;
    while (1)
    {
        visited[cur] = start;
        cur = choices[cur];

        if (visited[cur] == start)
        {
            while (visited[cur] != -1)
            {
                visited[cur] = -1;
                cur = choices[cur];
            }
            return;
        }
        else if (visited[cur] != 0)
        {
            return;
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);

    while (T--)
    {
        int n;
        scanf("%d", &n);

        fill(visited + 1, visited + n + 1, 0);

        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &choices[i]);
        }

        for (int i = 1; i <= n; i++)
        {
            if (visited[i] == 0)
            {
                search(n, i);
            }
        }

        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            if (visited[i] != -1)
            {
                cnt++;
            }
        }

        printf("%d\n", cnt);
    }

    return 0;
}
    [Sart]Boj 11652:カード
    完走していない選手-javascript