백준 11725번 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

노드의 개수가 100000개까지 이므로 인접리스트를 사용하는 것을 생각했고 루트부터 리프까지 탐색하기 위해 dfs를 사용했다.

인접리스트랑 dfs를 연습해볼 수 있었던 좋은문제!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class bj11725 {
	static int N;
	static ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
	static boolean [] visit;
	static int [] parent;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		visit = new boolean[N+1];
		parent = new int[N+1];
		for(int n=0;n<=N;n++) {
			list.add(new ArrayList<Integer>());
		}
		for(int n=1;n<N;n++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list.get(a).add(b);
			list.get(b).add(a);
		}
		makeTree(1);
		StringBuilder sb = new StringBuilder();
		for(int i=2;i<N+1;i++) {
			sb.append(parent[i]).append("\n");
		}
		System.out.println(sb);
	}
	static void makeTree(int index) {
		visit[index] = true;
		for(int v : list.get(index)) {
			if(visit[v]) continue;
			parent[v] = index;
			makeTree(v);
		}
	}
}