[백준 11725] 알고리즘 123일차 : 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

C++ 트리

트리의 정석

부모 자식 관계가 안알려진 간선 만 주어지고 각 노드의 부모를 출력하는 문제

 

접근방법

트리의 정석으로 풀이했다. vector로 인접리스트 사용했고 무방향그래프로 정의했고

루트노드인 1번 노드부터 BFS탐색하면서 자식 노드의 부모노드 정보를 parents배열에 저장했다.

 

오답노트

visit배열을 메인함수에서 선언해줘서 초기화를 안해줬다. 그랬더니 값이 true인 경우가 있었나보다. 전역변수로 빼줬더니 해결 

 

소스코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool visit[100001];

int main(){
    int n;
    cin >> n;
    
    vector<vector<int>> adj(n+1);
    queue<int> q;
    int parents[n+1];
    for(int i = 0 ; i < n-1 ; i++){
        int a,b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    q.push(1);
    visit[1] = true;
    parents[1] = 0;
    
    while(!q.empty()){
        int parent = q.front();
        q.pop();
        for(int i = 0 ; i < adj[parent].size() ; i++){
            int child = adj[parent][i];
            if(!visit[child]){
                visit[child] = true;
                q.push(child);
                parents[child] = parent;
            }
        }
    }
    
    for(int i = 2 ; i <= n ; i++){
        cout << parents[i] << "\n";
    }
    return 0;
}