백준 2668 숫자고르기(dfs with cycle graph)

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

2668번: 숫자고르기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 100 + 1;

int N, cnt;

int want[MAX];
bool visited[MAX];
vector<int> v;

bool done[MAX]; //방문이 끝났는지 여부

int numCycle;

void DFS(int nodeNum)

{

    visited[nodeNum] = true;

    int next = want[nodeNum];

    if (!visited[next])

        DFS(next);

    //이미 방문했지만 방문이 끝난 노드가 아니라면 사이클

    else if (!done[next])

    {

        //팀원을 모두 센다
        int i = next;
        v.push_back(i);
        while (i != nodeNum)
        {
            i = want[i];
            v.push_back(i);
        }
    }

    done[nodeNum] = true; //더 이상 해당 노드를 방문할 일이 없다
}

int main(void)

{

    cin >> N;

    for (int j = 1; j <= N; j++)

        cin >> want[j];

    cnt = 0;

    for (int j = 1; j <= N; j++)

        if (!visited[j])

            DFS(j); //팀을 이루는 사람들을 센다

    sort(v.begin(), v.end());
    cout << v.size() << "\n";
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << "\n";

    return 0;
}

cycle 문제를 최근에 풀어봤어서 이 문제가 cycle문제인지 또, 어떻게 풀어야 하는지 금방 알 수 있었다.

 

하지만, 만약에 좀 시간이 지난 다음 이 문제를 보았을 때 cycle문제임을 깨달을 수 있을까...?