트리의 부모찾기

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

#include <iostream>
#include <vector>

using namespace std;



bool findNoMore(int num, vector<vector<int>>&v, vector<int>&parent) {

	


	for (int i = 0; i < v[num].size(); i++ ) {
		
		if (parent[v[num][i]] ==0) {
			
			return false;
		
		}
	}
	return true;

}



void dfs(vector<int>&parent, vector<vector<int>>&v,int num) {


	if (findNoMore(num,v,parent)) {
		
		return;
		
	}


	for (int i = 0; i < v[num].size(); i++) {
		
		if (parent[v[num][i]] == 0) {
			parent[v[num][i]] = num;
			dfs(parent, v, v[num][i]);
		}
	}

	return;

}



int main() {
	

	ios_base::sync_with_stdio(0);

	cin.tie(0); //cin 속도 향상 위해

	int n;

	cin >> n;

	vector<vector<int>>v(n+1);
	vector<int>parent(n + 1,0);

	int a, b;

	parent[1] = -1;
	parent[0] = -1;

	for (int i = 0; i < n-1; i++) {
	
		cin >> a;
		cin >> b;

		v[a].push_back(b);
		v[b].push_back(a);
	
	}

	dfs(parent,v,1);

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



}