트리의 부모 찾기 - 백준 11725

Problem

실버 2 문제

분류
그래프 탐색 문제, 트리

 

접근

DFS(탐색용), Adj List(V = E), 무방향 그래프 표현, 구조체 이용

 

몰랐던 것 및 까먹은 부분

1) 트리에는 루트 노드가 원래 없다.

2) "\n"

3) 

ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

 

Solution

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int n;
struct node {
    int parent = -1;
    bool visited = false;
    vector<int> linked;
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    vector<node> nodes(n);
    for (int i = 0; i < n - 1; i++) {
        int a;
        int b;
        cin >> a >> b;
        nodes[a - 1].linked.push_back(b - 1);
        nodes[b - 1].linked.push_back(a - 1);
    }
    vector<int> q;
    q.push_back(0);
    nodes[0].visited = true;
    int cnt = 0;
    while(!q.empty()){
        cnt++;
        int idx = q.back();
        q.pop_back();
        for (int u : nodes[idx].linked) {
            if (nodes[u].visited != true) {
                nodes[u].visited = true;
                q.push_back(u);
                nodes[u].parent = idx;
            }
        }
    }
    for (node n : nodes) {
        if (n.parent != -1) {
            cout << n.parent + 1 << "\n";
        }
    }
}