[9466] 텀 프로젝트

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

9466번: 텀 프로젝트

<문제>

프로젝트 팀에 속한 학생의 수를 cnt에 저장하고, (전체 학생수-cnt)를 출력하면 된다.

하나의 사이클을 이루는 경우를 세어야 하는데, 이 부분을 재귀적으로 탐색해나가면 된다.

사이클을 한번 돈 다음에는, 몇개의 노드로 구성된 사이클인지를 판별해야 하고,

사이클 판별여부와 방문진행 여부를 별도로 분리하여 저장하기 위해서

각각 check와 visit이라는 bool형 배열을 만들어서 구현해주었다.

 

<소스코드>

#include<stdio.h>
#include<string.h>
int a[100001];
bool check[100001];
bool visit[100001];
int cnt = 0;
void dfs(int cur)
{
    visit[cur] = true;
    int next = a[cur];
    if (!visit[next]) dfs(next);
    if (!check[next]){
        for (int i = next; i != cur; i = a[i]) cnt++;
        cnt++;
    }
    check[cur] = true;
    return;
}
int main(void) {
    int t, i, j, n=0;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (i = 1; i <= n; i++) {
            a[i]=visit[i] = check[i] = 0;
            scanf("%d", &a[i]);
        }
        cnt = 0;
        for (i = 1; i <= n; i++) {
            if (visit[i] == false)
                dfs(i);
        }
        printf("%d\n",n-cnt);
    }
    return 0;
}