DFS 문제 분석-4(텀 프로젝트 boj_9466)

1. 텀 프로젝트 문제 분석(boj.kr/9466)

#include <cstdio>
#include <algorithm>
using namespace std;
 
#define MAX_SIZE 100001
 
int N, edge[MAX_SIZE], cnt;
bool visited[MAX_SIZE], finished[MAX_SIZE];
 
/*다음에 방문할 정점을 방문한 적 있는데, DFS가 끝나지 않는다면
(사이클), 다음에 방문 할 정점부터, 나한테 돌아올때까지 더한다.
그리고 마지막에 나를 포함하기 위해서 cnt++을 해준다.
*/
 
void dfs(int cur) {
    visited[cur] = true;//들어온 idx 방문.
    int next = edge[cur];//cur이 가르키는 정점==next.
 
    if (visited[next]) {//만약 다음 노드를 방문했는데, 
        if (!finished[next]) {//DFS가 계속 끝나지 않는다면, 
            for (int temp = next; temp != cur; temp = edge[temp]) cnt++;
            cnt++;//그 다음노드부터, 다시 cur로 돌아올때까지 cnt++;
            //마지막은 자기자신.
        }
    }
 
    else dfs(next);//다음노드 방문 안됐으면, 다음노드를 dfs.
    finished[cur] = true;
}
 
int main(void) {
    int testcase;
    scanf("%d", &testcase);
 
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &edge[i]);
        }
        
        fill(visited, visited + N + 1 , false);//visited 행렬 0~N+1 0으로
        fill(finished, finished + N + 1 , false);//finished 행렬 0~N+1 0
 
        for (int i = 1; i <= N; ++i) {//방문하지 않았으면 DFS.
            if (!visited[i]) dfs(i);
        }
 
        printf("%d\n", N - cnt);
        cnt = 0;
    }
 
    return 0;
}

이후 추가.