백준 9466번 텀 프로젝트

백준  9466번 텀 프로젝트

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring> //memset
using namespace std;
const int MAX = 100000 + 2;
int cases;
int N;
int arr[MAX];
int visited[MAX];
int cnt;
 
int roop2(int start,int res,int count,int dest) {
    if (start == res) {
        return count;
    }
    if (count == dest) return dest;
 
    roop2(arr[start], res, count + 1, dest);
}
//사이클이 이루어 지는 사이클 개수를 반환한다.
int roop(int start, int res,int count) {
    //입력값부터 사이클시작하는경우
    if (visited[start]==1&&res==start)
        return count;
    //1 2 3 7 8 3 같은 경우 입력값은 1로 시작하지만
    //중간에 사이클이 만들어지는데 
    //이런 경우를 고려해서 사이클 개수를 반환한다.
    else if (visited[start]&&start != res) {
        int a=roop2(res,start,0,count);
        return count - a;
    }
    visited[start] = 1;
    roop(arr[start], res,count+1);
}
 
 
int main(void)
{
    cin >> cases;
    while (cases--) {
        memset(arr, 0, sizeof(arr));
        memset(visited, 0, sizeof(visited));
        cin >> N;
        for (int i = 1; i <= N; i++) {
            cin >> arr[i];
        }
        cnt = N;
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                cnt-=roop(i, i, 0);
            }
        }
        cout << cnt << endl;
    }
 
    return 0;
}

출처:https://www.acmicpc.net/problem/9466

사이클이 언제 이뤄지는 지 잘 생각해서 풀어야 하는 문제였습니다.

1 2 3 4 5 6 7 8 9 3 인 경우는 시작은 1로 했어도, 중간에 사이클이 만들어지고 1 2의 경우는 

단방향으로 가는 문제에서 요구하는 개수 입니다. 

전체 인원에서 사이클의 크기를 계속해서 제거해주어서, 출력하는 방식으로 구현을 했습니다.