[백준] 9466번*

• 사이클에 포함되어 있지 않은 원소의 개수 구하기
• 임의의 원소에서 시작해 사이클에 포함된 원소인지/아닌지 체크 -> 저장

💻 C++ 기반

https://www.acmicpc.net/problem/9466

✔️ visited 배열에 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;
}