[BOJ] 9466번: 텀 프로젝트

문제 링크:

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

접근법:

a가 b랑 팀을 하고싶다는 관계를 간선으로 볼 때
전체적인 관계는 그래프로 생각할 수 있고,
s1이 s2를 선택
s2가 s3을 선택
...
sr-1이 sr을 선택
sr이 s1을 선택
싸이클이다!
싸이클에 속하는 정점들의 개수를 구하고 N에서 빼면된다.

코드:

#include <iostream>
#include <stack>
#include <cstring>

using namespace std;

typedef long long ll;

int visited[100001], finished[100001], N, S[100001], ans, T;
stack<int> st;

void dfs(int curr){
    visited[curr] = true;
    st.push(curr);
    if(visited[S[curr]] == false)
        dfs(S[curr]);
    else if(finished[S[curr]] == false)
        while(true){
            int front = st.top();
            st.pop();
            ans--;
            if(front == S[curr])
                break;
        }
    finished[curr] = true;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> T;
    while(T--){
        cin >> N;
        ans = N;
        st = stack<int>();
        memset(finished, 0, sizeof(finished));
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < N; i++){
            cin >> S[i];
            S[i]--;
        }
        for(int i = 0; i < N; i++)
            dfs(i);
        cout << ans << "\n";
    }
}