백준 9466. 텀 프로젝트

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

다시 푼 문제, 이전 글 : tose33.tistory.com/25

 

#include <iostream>
using namespace std;
#include <cstring>
#define MAX 100001

int edge[MAX];
int group[MAX];
int cnt[MAX];
int group_idx = 1;
int cnt_idx = 1;
int res = 0;

void initData() {
    group_idx = 1;
    cnt_idx = 1;
    res = 0;

    memset(edge, 0, sizeof(edge));
    memset(group, 0, sizeof(group));
    memset(cnt, 0, sizeof(cnt));
}

void dfs(int n) {
    if(cnt[n] > 0) {
        if(group[n] == group_idx) { // 같은 그룹 : 팀결성
            res += cnt_idx - cnt[n]; // 팀을 이룬 인원 갱신
        }
        else { // 다른 그룹

        }
        return;
    }

    group[n] = group_idx;
    cnt[n] = cnt_idx;
    cnt_idx++;

    dfs(edge[n]);
}

int main() {
    int T;
    cin >> T;

    while(T--) {
        initData();

        int N;
        cin >> N;
        for(int i = 1; i <= N; i++) cin >> edge[i];

        for(int i = 1; i <= N; i++) {
            if(cnt[i] == 0) { // 방문하지 않은 정점만 dfs 수행
                cnt_idx = 1;
                dfs(i);
                group_idx++;
            }
        }

        cout << N - res << endl;
    }



}