[백준] 9466번*
- 사이클에 포함되어 있지 않은 원소의 개수 구하기
- 임의의 원소에서 시작해 사이클에 포함된 원소인지/아닌지 체크 -> 저장
💻 C++ 기반
✔️ 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;
}
Author And Source
이 문제에 관하여([백준] 9466번*), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jieun_han/백준-9466번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)