[C++]백준 - 11725번 문제

[C++]백준 - 11725번 문제

11725번: 트리의 부모 찾기 (acmicpc.net)

11725번 : 트리의 부모 찾기

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

생각해 볼 점

* 트리는 순환이 없는 그래프입니다.

* 순환이 없으므로 루트에서 탐색을 시작하면, 다음 노드는 반드시 이전 노드의 자식입니다.

이 두 가지만 숙지하면, 문제를 푸는 데에 문제가 없습니다.

코드

#include #include #include using namespace std; int main() { int N; scanf("%d", &N;); //동적 할당 vector *graph = new vector[N + 1]; bool *visited = new bool[N + 1]; int *parent = new int[N + 1]; fill_n(visited, N + 1, false); fill_n(parent, N + 1, 0); parent[1] = -1; //입력부 for(int i = 1; i < N; i++) { int a, b; scanf("%d %d", &a;, &b;); graph[a].push_back(b); graph[b].push_back(a); } //BFS알고리즘 queue q; q.push(1); visited[1] = true; while(!q.empty()) { int current = q.front(); q.pop(); //루트에서 아래로 내려가므로, 다음 간선은 current의 자식임 for(int next : graph[current]) { if(!visited[next]) { parent[next] = current; q.push(next); visited[next] = true; } } } for(int i = 2; i < N + 1; i++) printf("%d

", parent[i]); delete[] graph; delete[] visited; delete[] parent; return 0; }

그 외

from http://popoli31.tistory.com/101 by ccl(A) rewrite - 2021-09-18 19:26:46