백준 11725번: 트리의 부모 찾기 [트리][재귀][그래프] -Java

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

11725번: 트리의 부모 찾기

package algorithm.boj;

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

public class Boj11725 {

	public static List<Integer> graph[];
	public static int N;
	public static int ans[];
	public static boolean visit[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		ans = new int[N+1];
		visit = new boolean[N+1];
		graph = new ArrayList[N+1];
		
		for (int i = 0; i < N+1; i++) {
			graph[i] = new ArrayList<Integer>();
		}
		
		for (int i = 0; i < N-1; i++) {
			st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			
			//무방향 그래프이므로 양쪽 다 넣어줌
			graph[n1].add(n2);
			graph[n2].add(n1);
		}
		
		visit[1] = true;
		fun(1);
		
		for (int i = 2; i < ans.length; i++) {
			System.out.println(ans[i]);
		}
	}
	
	public static void fun(int idx) {
		if(graph[idx].size() == 1)
			return;
		
		for (int i = 0; i < graph[idx].size(); i++) {
			if(visit[graph[idx].get(i)])
				continue;
			
			visit[graph[idx].get(i)] = true;
			ans[graph[idx].get(i)] = idx; //부모 답
			fun(graph[idx].get(i));
		}
	}

}