067 : 트리의 부모 찾기

 

 

 

 

 

 

 

BFS 흐름에 parent 리시버 Pair만 해주면 된다

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

DFS로 가능한 것도 참고할 것

 

 

 

 

 

 

 

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static ArrayList<Integer>[] TP;
    static int[] parent;
    static boolean[] visited;

    public static void main(String[] args) {

        // ISC
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();

        // D2F
        TP = new ArrayList[V+1];
        for (int i = 1; i <= V; i++) {
            TP[i] = new ArrayList<>();
        }
        for (int i = 1; i <= V; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            TP[s].add(e);
            TP[e].add(s);
        }

        parent = new int[V+1];
        visited = new boolean[V+1];

        // OP
        DFS(1);

        // OEC
        for (int i = 2; i <= V; i++) {
            System.out.println(parent[i]);
        }

    }

    static void DFS(int now) {

        visited[now] = true;

        for (int connected : TP[now]) {
            if (!visited[connected]) {
                visited[connected] = true;
                DFS(connected);
            }
        }
    }
}