백준 11725 트리의 부모 찾기

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

그래프에 입력받고 DFS이던 BFS이던 해준 뒤에 2부터 N까지의 부모 노드를 저장해주면 된다.

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

vector<vector<int>> ar;
bool vis[100001];
map<int, int> M;

void dfs(int cur) {
	vis[cur] = true;
	for (auto i : ar[cur]) {
		if (!vis[i]) {
			M[i] = cur;
			dfs(i);
		}
	}
}

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

	int n;
	cin >> n;
	ar.resize(n + 1);
	for (int i = 0; i < n - 1; i++) {
		int x, y; cin >> x >> y;
		ar[x].push_back(y);
		ar[y].push_back(x);
	}
	dfs(1);

	for (auto i : M) {
		cout << i.second << '\n';
	}

	return 0;
}

map도 연습해볼 겸 사용해봤다.