11725: 트리의 부모 찾기

[minsoo0715]

11725: 트리의 부모 찾기

소스 코드

아이디어

하위 노드들이 루트 노드 밑에 어떻게 생길지 모르기 때문에, 루트 노드로부터 노드 탐색이 필요하다.
각 노드들의 연결된 노드를 배열에 기록해놓고, 방문한 노드를 제외하고 탐색을 한다.
이때 방문하기전에 현재 노드를 정답으로 기록한다.

구현

연결된 노드가 기록된 배열을 순회하고, 방문하지 않은 노드라면 하위 노드에 대한 부모 노드를 저장 후, 재귀 호출을 통해 모든 노드를 방문한다.

void solve(int num = 1) {
    visited[num] = true;

    for(int i : v[num]) {
        if(!visited[i]) {
            ans[i] = num;
            solve(i);
        }
    }
}