[백준/C++] 9466번 텀 프로젝트

문제: www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

 

문제풀이

 

이 문제에서 프로젝트 팀이라는 것은 그래프의 사이클을 뜻한다.

사이클에 속하지 못한 노드들의 개수를 구하는 문제이다.

 

visited 배열을 선언해 0이면 방문하지 않은 노드, -1이면 사이클에 속하는 노드, 0과 -1이 아닌 다른 숫자이면 방문은 했으나 사이클에 속하지 못하는 노드를 뜻한다.

 

노드 하나하나를 모두 사이클에 속하는지 검사하면 시간 초과로 문제를 틀리게 된다. 때문에 한 번 방문할 때 연결된 노드들을 다시 방문해서는 안된다.

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int visited[100001];
int link[100001];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int t;
    cin>>t;

    while(t--){
        int n;
        cin>>n;

        fill(visited, visited+n+1, 0); //다음 테스트케이스를 위해 초기화

        for(int i=1; i<=n; i++){
            cin>>link[i];
        }

        for(int i=1; i<=n; i++){
            if(visited[i] != 0) continue; //방문한 적이없는 노드만 탐색

            int cur = i;
            visited[i] = i;

            while(true){
                cur = link[cur];

                if(visited[cur] == i){ //사이클로 인해 같은 i값을 가지고 있다면
                    while(visited[cur] != -1){ //해당 사이클의 노드들을 모두 -1로 초기화
                        visited[cur] = -1;
                        cur = link[cur];
                    }
                    break;
                }
                if(visited[cur] == 0){ //방문한 적 없다면
                    visited[cur] = i;
                    continue;
                }
                else break; //방문했었다면 break
            }

        }

        int result = n;
        for(int i=1; i<=n; i++){
            if(visited[i] == -1) //-1의 개수만큼 n에서 빼준다.
                result--;
        }

        cout<<result<<"\n";
    }
    
    return 0;
}

 

 

결과