2668번

2668번 - 숫자고르기

결국 문제에서 핵심은, 입력값이 노드와 그 노드에 연결되는 노드라고 했을 때

싸이클의 갯수와 싸이클에 포함되는 노드들을 모두 구하면 된다.

싸이클을 구하는 방법은 discoverd 배열과 finished 배열을 이용해서 역방향 간선을 구하면 된다.

어떠한 정점이 발견됐을 때, 이미 발견된 정점이지만 finished 가 false 이면 역방향 간선이 된다.

(나의 참고자료에 내 필기가 있음)

이렇게 역방향 간선이 이루어지는 경우, 싸이클을 이루게 된다.

처음에 고민했던 점은 A->B->C->D->B 이런 싸이클이 있을 때, BCD만 어떻게 뽑아낼 것인가를 고민했는데,

그냥 재귀함수가 끝나는 시점에서 싸이클의 시작점을 체크하는 방법으로 문제를 풀 수 있었다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
 
int n;
int v[101];
int d[101];
bool f[101];
queue<int> q;
vector<int> c;
bool cycle = true;
 
void dfs(int now)
{
    int next = v[now];
 
    if ((d[next]!=0 && d[next] < d[now] && !f[next]) || next==now)
    {
        cycle = true;
        d[next] = -1;
    }
 
    if (d[next] == 0)
    {
        d[next] = d[now] + 1;
        dfs(next);
    }
    
    if (cycle)
    {
        c.push_back(now);
        if (d[now] == -1)
        {
            cycle = false;
        }
    }
    f[now] = true;
    return;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (d[i]==0)
        {
            cycle = false;
            d[i] = 1;
            dfs(i);
        }
    }
 
    sort(c.begin(), c.end());
 
    cout << c.size() << "\n";
    for (int i = 0; i < c.size(); i++)
    {
        cout << c[i] << "\n";
    }
 
    return 0;
 
}