[BOJ 9466] 텀 프로젝트

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

dfs의 사이클을 체크하여 사이클의 경우 dfs를 돌리지 않고 최적화 하는 방법으로 시간을 줄이는 문제이다. 

찬란한 오답 퍼레이드 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

dfs상에서 사이클을 체크하는 방법은 아직 끝나지 않았지만 visit된 정점을 방문할경우 사이클이 존재한다고 생각하는 것이다. 

#include<iostream>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<utility>
#include<vector>
#include<cstring>
#include<queue>
#include<cmath>
#include<math.h>
 
using namespace std;
 
int par[100100];
int t, n, arr[100100], res;
int visited[100010];
int finish[100010];
void cycle(int v, int p){
    res++;
    if (v == p){
        return;
    }
    cycle(par[v], p);
}
void dfs(int v){
    visited[v] = true;
    if (!visited[arr[v]]){
        par[arr[v]] = v;
        dfs(arr[v]);
    }else if (!finish[arr[v]]){  //방문은 되었으나 finisi함수가 되지 않았으면 사이클 체크가 되어있지 않다면
        cycle(v, arr[v]);
    }
    finish[v] = true;
}
int main(){
    scanf("%d", &t);
    while (t--){
        memset(par, -1, sizeof(par));
        memset(visited, 0, sizeof(visited));
        memset(finish, 0, sizeof(finish));
        res = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++){
            scanf("%d", &arr[i]);
        }
        for (int i = 1; i <= n; i++){
            if (!visited[i]){
                dfs(i);
            }
        }
        printf("%d\n", n - res);
    }
    return 0;
}

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220785731077

갓퍼마리오님의 설명을 참고한다면 더 쉽게 접근할 수 있을것이다.