<백준> 11725

트리의 부모 찾기

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

입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

부모노드를 담긴 위한 arr를 하나 선언해 출력하도록 했다.

#define MAX 100001

int n;
vector<int> tree[MAX];
bool visited[MAX];
int arr[MAX];

void dfs(int x)
{
	visited[x] = true;
	for (int i = 0; i < tree[x].size(); i++)
	{
		int next = tree[x][i];
		if (!visited[next])
		{
			arr[next] = x;
			dfs(next);
		}
	}
}

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

	cin >> n;

	for (int i = 0; i < n-1; i++)
	{
		int x, y;
		cin >> x>>y;

		tree[x].push_back(y);
		tree[y].push_back(x);
	}
	dfs(1);

	for (int i = 2; i <= n; i++)
	{
		cout << arr[i] << "\n";
	}
}