BOJ 2668 : 숫자고르기

• 문제 링크 : boj.kr/2668
• 난이도 : G5
• 태그 : DFS

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<int> arr(n+1);
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    int cnt = 0;
    vector<int> visit(n+1, -1);
    vector<int> ans(n+1, 0);
    for(int i = 1; i <= n; i++) {
        int curr = i;
        int next = arr[curr];
        visit[curr] = i;
        while(visit[next] != i) {
            visit[next] = i;
            curr = next;
            next = arr[curr];
        }
        if(next == i) {
            cnt++;
            ans[i] = 1;
        }
    }
    cout << cnt << "\n";
    for(int i = 1; i <= n; i++) {
        if(ans[i] == 1) cout << i << "\n";
    }
s
    return 0;
}

---

풀이

n이 100으로 매우 작기 때문에 모든 정수에 대해 DFS로 사이클 판단을 하면 된다. 사이클 판단의 경우 자기 자신으로 돌아오는 경우만 세면 된다.