링크
https://www.acmicpc.net/problem/11725
풀이방법
해당 문제는 dfs를 이용하여 완전 탐색과, p라는 배열을 만들어서 p[i]=j i의 부모는 j라는 의미를 사용하여 문제를 해결 할 수 있다.
코드
#include <bits/stdc++.h>
using namespace std;
int p[100'005];
vector<int> adj[100'005];
int n;
void dfs(int cur)
{
for (auto nxt : adj[cur])
{
if (p[cur] == nxt) continue;
p[nxt] = cur;
dfs(nxt);
}
}
int main()
{
cin >> n;
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1);
for (int i = 2; i <= n; i++)
{
cout << p[i] << '\n';
}
}
'CS(Computer Science)지식 > [C++][코딩 테스트] 자료구조 및 알고리즘' 카테고리의 다른 글
백준 4803번: 트리 (C++) (0) | 2024.02.02 |
---|---|
백준 1991번: 트리 순회 (C++) (0) | 2024.02.02 |
백준 11403번: 경로 찾기 (C++) (0) | 2024.02.02 |
백준 5667번: 결혼식 (C++) (0) | 2024.02.02 |
백준 1260번: DFS와 BFS (C++) (0) | 2024.02.02 |