숫자고르기 2668

문제

접근 방법

이런 형식이더라도 1, 3, 5는 같은 집합일 것이다.
쭉 숫자를 따라가서 시작한 곳으로 다시 돌아올 때 같은 집합으로 판정되는 것이다.

코드

#include <iostream>
#include <vector>
using namespace std;
vector<bool> isVisted;
vector<int> graph, ret;
void dfs(int cur, int start)
{
    if (isVisted[cur])
    {
        if (cur == start)
            ret.push_back(cur);
    }
    else
    {
        isVisted[cur] = true;
        dfs(graph[cur], start);
    }
}
int main()
{
    int N;
    cin >> N;
    graph = vector<int>(N + 1);
    for (int i = 1; i <= N; ++i)
    {
        cin >> graph[i];
    }
    for (int i = 1; i <= N; ++i)
    {
        isVisted = vector<bool>(N + 1);
        dfs(i, i);
    }
    cout << ret.size();
    for (int i : ret)
    {
        cout << "\n"
             << i;
    }
}

풀이

방문한 곳을 저장해두고 시작 지점으로 다시 오면 그 부분들을 추가해주는 방식을 하려다가 시간을 잡아먹었다. 방문한 곳을 다시 방문 안 하려면 bool로 체크해줘야 하는데 그럴 경우 예제에서의 2-1과 같은 부분도 섞여버린다.
그냥 DFS할 때마다 bool을 초기화하는 지금 방식을 쓰는 것이 단순하고 좋은 것 같다.