[BFS/DFS] C11 백준 9466 텀 프로젝트 풀이

문제

• 9466

풀이 과정

• 이 문제는 사이클에 속하지 않는 친구들을 찾는 문제
• 1 2 3 4 5 6 7 의 학생이
• 3 1 3 7 3 4 6 으로 찍었을 때
  • 1, 2, 5 는 사이클에 속하지 못 함 -> 출력값
  • 자기 자신으로 돌아와야 1사이클로 쳐줌
  • 자기 자신으로 돌아오지 않는다면 사이클이 아님
  • 사이클이 완료됐다면 해당 visit는 2로 탐색 완료
    • 이 조건에서 자기자신을 포함해야 하는 조건 추가

#include <stdio.h>

#define MAX_LEN 100001

int n;
int student[MAX_LEN];
int visit[MAX_LEN];

int cyclecnt(int start, int end) {
    int cnt = 0;
    for (int i=start; i!=end; i=student[i]) {
        cnt++;
    }
    return cnt + 1;
}

int dfs(int x) {
    int cnt = 0;
    
    visit[x] = 1;
    int nx = student[x];
    
    if (visit[nx] == 0) {
        cnt += dfs(nx);
    } else if (visit[nx] == 1) {
        cnt += cyclecnt(nx, x);
    }
    visit[x] = 2;
    
    return cnt;
}

int main() {
    int tc;
    scanf("%d", &tc);
    
    while (tc--) {
        scanf("%d", &n);
        
        for (int i=1; i<=n; i++) {
            visit[i] = 0;
        }
        
        for (int i=1; i<=n; i++) {
            scanf("%d", &student[i]);
        }
        
        int cnt = 0;
        for (int i=1; i<=n; i++) {
            if (visit[i] == 0) {
                cnt += dfs(i);
            }
        }
        
        printf("%d\n", n - cnt);
    }
    
    return 0;
}