(11725) 트리의 부모 찾기

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

단계별로 풀어보기

33단계(트리) 1번째

 

 

 

특수한 그래프의 형태 중 하나인 트리다. 일종의 희소 그래프라 인접 리스트가 비효율적이다. 노드 구조체를 만들어 트리를 직접 구현하는 등 다른 방식도 있지만, 쉬운 문제에서는 그래프 문제처럼 풀어도 충분하다.

 

 

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n;
  
  cin >> n;
  
  vector adj(n+1, vector<int> ());
  vector<int> visited(n+1, -1);
  queue<int> q;
  
  for(int i=1;i<n;i++){
    int u, v;
    
    cin >> u >> v;
    
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  q.push(1);
  
  while(!q.empty()){
    int now= q.front();
    q.pop();
    
    for(int next:adj[now]){
      if(visited[next]!=-1)  continue;
      
      visited[next]= now;
      q.push(next);
    }
  }

  for(int i=2;i<=n;i++)  cout << visited[i] << "\n";
  
  return 0;
}