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

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

1)문제분류

- 트리

2)문제 해결

-각 정점을 서로 연결 짓는다.

- 루트 1에서 시작하여 BFS로 탐색하여 노드들의 부모를 파악한다

  (큐에서 꺼낸 노드가 연결된 방문할 다음 노드의 부모가 되는 구조)

- 부모 배열 p를 만들어서 큐 탐색시에 자식과 부모관계 적기

   1 -2 -3  (1은 2의 부모 2는 3의 부모..)

#include<iostream>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

//레벨 순회

int n,x,y;

vector<int>vt[100002];

int p[100002];

bool chk[100002];

void bfs()

{

queue<int>pq;

pq.push(1); //루트노드

chk[1] = true;

while (!pq.empty())

{

int out = pq.front();

pq.pop();

for (int i = 0; i < vt[out].size(); i++)

{

int next = vt[out][i];

if (chk[next] == false)

{

chk[next] = true;

p[next] = out; //next의 조상은 out

pq.push(next);

}

}

}

}

int main()

{

cin >> n;

for (int i = 0; i < n; i++)

{

cin >> x >> y;

vt[x].push_back(y);

vt[y].push_back(x);

}

bfs();

for (int i = 2; i <= n; i++)

cout << p[i] << '\n';

}