[C++] 9466번 텀 프로젝트 - DFS, 위상 정렬, union-find

#include <iostream>
#include <vector>
#include <string.h>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_N 100001

using namespace std;

int T, n;  //테스트 케이스의 개수 T, 사람의 수 n
int num[MAX_N];  //선택한 학생
int vi[MAX_N], fi[MAX_N];  //visited, finished
int ord[MAX_N];  //탐색된 순서
int cnt;
int res;

void input()
{
    cin >> n;
    LOOP(i, n) cin >> num[i];
}

void dfs(int no)  //node
{
    if(fi[no])
        return;
    if(vi[no]) {
        res += cnt - ord[no];  //사이클을 발생시킬 경우 탐색된 순서의 차이가 사이클을 구성하는 노드의 개수
        return;
    }
    ord[no]=cnt++;  //탐색된 순서 기록
    vi[no]=1;
    
    dfs(num[no]);
    fi[no]=1;  //탐색이 다끝나면 더 이상 보지 않음
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> T;
    LOOP(i, T) {
        res=0;  //초기화
        memset(vi, 0, sizeof(int)*MAX_N);
        memset(ord, 0, sizeof(int)*MAX_N);
        memset(fi, 0, sizeof(int)*MAX_N);
        
        input();
        
        LOOP(i, n) {
            cnt=0;
            if(!fi[i])
                dfs(i);
        }
        cout << n-res << '\n';
    }
    
    return 0;
}

 

<시행착오>

1. 맨 처음에 한 노드에서 여러 개의 간선이 뻗어나가는 줄 알았다. 그렇지 않고 하나의 간선만 뻗어져 나간다.
2. 한 번 방문했던 거랑, 아예 탐색이 끝난 거랑 순서를 잘 맞춰야 한다.

 

시간이 평균보다 약간 더 많이 걸렸다. 아마 메모리 초기화하는 memset 때문인 것 같은데 fi와 vi를 하나로 합치면 더 줄일 수 있는 것 같다. 

 

합쳐진 코드를 짠 사람이 있길래 가져왔다.

 

<DFS로 cycle 찾기>

https://hongjw1938.tistory.com/42

알고리즘 - 그래프 탐색(깊이 우선 탐색 - DFS)

 

<fi와 vi 합친 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/board/view/47849

글 읽기 - 테스트 케이스 올려봅니다

 

<반례 모음>

https://www.acmicpc.net/board/view/47849

글 읽기 - 테스트 케이스 올려봅니다

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.