백준 11725번 : 트리의 부모 찾기

문제 접근

---

트리 만들어서 노드1 부터 탐색하고, 연결되어있는 노드가 부모가 아니라면 해당 노드를 연결되어있는 노드의 부모로 설정하는 방식으로 풀었다.

 

분명 제대로 풀고, 머리 속에서 여러번 돌려봤는데 출력이 안 돼서 뭐가 문제인지 확인해보니까, while(--N) 으로 구현해서 for(int i=2; i<=N; ++i) 에서 안 돌아갔던 거였다.

 

실수를 줄이세요, AeonFlor.

 

 

문제 코드

---

#include <iostream>
#include <vector>

using namespace std;

// s : 연결된 두 정점의 시작 부분, e : 연결된 두 정점의 끝 부분
// tree : 트리 구현
int N, s, e;
vector<vector<int>> tree(100000);
int parent[100001] = {0};

void link(int node)
{
	//cout<<node<<" : "<<tree[node].size()<<'\n';
	
	for(int i=0; i<tree[node].size(); ++i)
	{
		if(tree[node][i] != parent[node])
		{
			parent[tree[node][i]] = node;
			//cout<<node <<" -> "<<tree[node][i]<<", parent : "<<parent[tree[node][i]]<<'\n';
			link(tree[node][i]);
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>N;
	
	for(int i=1; i<N; ++i)
	{
		cin>>s>>e;
		tree[s].push_back(e);
		tree[e].push_back(s);
	}
	
	link(1);
	
	for(int i=2; i<=N; ++i)
		cout<<parent[i]<<'\n';
}