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

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

포인트

- 트리 정의하기 -> 인접리스트 사용: 벡터를 사용하기

- 트리 순회하기 -> bfs: 큐를 사용하여 모든 노드를 순회한다.

 

- 주의: 매번 검색하면 시간 초과가 난다. 한번 순회하면서 부모노드를 모두 저장한다.

#include <stdio.h>
#include <vector>
#include <queue>
#define MAX 100000 + 1

using namespace std;
vector<int> v[MAX];
int result[MAX];

int root = 1;

void findParent()
{
  queue<int> q;
  int flag[MAX] = {
      0,
  };
  q.push(root);
  flag[root] = 1;

  while (!q.empty())
  {
    int cur = q.front();
    q.pop();

    for (int i = 0; i < v[cur].size(); i++)
    {
      int nxt = v[cur][i];
      if (flag[nxt])
        continue;

      result[nxt] = cur;

      q.push(nxt);
      flag[nxt] = 1;
    }
  }
}

int main(void)
{
  int n;
  scanf("%d", &n);

  for (int i = 0; i < n; i++)
  {
    int x, y;
    scanf("%d %d", &x, &y);
    v[x].push_back(y);
    v[y].push_back(x);
  }

  findParent();

  for (int i = 2; i <= n; i++)
  {
    printf("%d\n", result[i]);
  }

  return 0;
}