트리의 부모 찾기

---

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

---

1. 그래프의 간선들이 주어지므로, 루트노드가 1번인것을 이용하여 트리를 구성한다.
2. DFS와 BFS를 이용하여 트리를 구성해나간다. 여기서는 DFS로 풀이를 진행하였다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>

using namespace std;
#define endl "\n"

#define MAX 100000+1
int N;
vector<int> graph[MAX];
bool visited[MAX];
int ans[MAX];

void dfs(int v) {
	visited[v] = true;

	for (int i = 0; i < graph[v].size(); i++)
	{
		int parent = v;
		int child = graph[v][i];
		if (!visited[child])
		{
			visited[child] = true;
			ans[child] = parent;
			dfs(child);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int x, y;
		cin >> x >> y;
		grape[x].push_back(y);
		grape[y].push_back(x);
	}

	dfs(1);

	for (int i = 2; i <= N; i++)
	{
		cout << ans[i] << endl;
	}

}