[백준 10552번] [DFS] DOM

Approach

DFS를 통해 트리의 높이를 추적하는 느낌이다. 다만, 사이클이 발생하는 경우에만 -1을 출력해주면 된다.

사이클이 발생하는 상황은 방문한 곳에 다시 방문을 시도하려고 할 때, -1을 출력해주면 된다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int n, m, p;
int visited[100001];
int v[100001];
int r[100001];

int dfs(int c){
    visited[c] = 1;
    if(v[c] == -1) return 0;
    int cur = r[v[c]];
    int result = 0;
    if(!visited[cur]){
        int val = dfs(cur);
        if(val == -1) return -1;
        else
            result += val;
    }
    else return -1;
    return result + 1;
}

int main(void){
    fastio;
    memset(v, -1, sizeof(v));
    memset(visited, 0, sizeof(visited));
    cin >> n >> m >> p;

    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        r[i] = a;
        if(v[b] == -1) v[b] = i;
    }

    cout << dfs(p) << "\n";
    return 0;
}