[백준 11725번] 트리의 부모 찾기

문제 링크: https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

<문제 풀이> 그래프, 트리, DFS, BFS

 

트리는 그래프의 특수한 형태이므로 그래프 탐색을 그대로 사용하면 됩니다. 노드 1을 시작으로 bfs를 돌리면 되는데, 각 노드의 인접한 노드들을 큐에 넣을 때는 부모를 제외한 자식 노드들만 넣으면 됩니다. 왜냐하면 큐에서 꺼낸 각 노드의 부모는 이전에 이미 방문했기 때문입니다. 

<C++ 소스 코드>

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
vector<int>adj[100001];
int parents[100001];
int n;
 
void bfs() {
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto& next : adj[cur]) {
            if (parents[cur] == next)continue;
            q.push(next);
            parents[next] = cur;
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    bfs();
 
    for (int i = 2; i <= n; i++) {
        cout << parents[i] << '\n';
    }
 
    return 0;
}