Beakjoon 9466 텀 프로젝트

26 Jan 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/9466

나의 풀이

그래프가 싸이클을 형성할 때 까지 탐색, 한 번 탐색할 때 싸이클에 포함되지 않았던 정점의 개수를 Count한다.

풀이 코드 : 9466 텀 프로젝트

#include <stdio.h>
#include <vector>

using namespace std;

vector<int> map;
vector<int> visit;
int solution(int start){
    int count = 0;
    int curr = start;
    vector<int> stack;
    while(!visit[curr]){
        stack.push_back(curr);
        visit[curr] = 1;
        curr = map[curr];
    }
    for(int i=0;i<stack.size();i++){
        if(stack[i] == curr){
            break;
        }
        count++;
    }
    return count;
}

int main(){
    int T, n;
    scanf("%d", &T);

    for(int t=0;t<T;t++){
        scanf("%d", &n);
        map.resize(n+1);
        visit.resize(n+1);
        for(int i=1;i<=n;i++){
            scanf("%d", &map[i]);
        }
        int answer = 0;
        for(int i=1;i<=n;i++){
            answer += solution(i);
        }

        printf("%d\n", answer);
        visit.clear();
        map.clear();
    }
}

채점결과