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

質問する

根のない木をあげます.ツリーのルートディレクトリが1の場合、各ノードの親ノードを解くプログラムを作成します.

入力

第1行は、ノード数N(2≦N≦100000)を与える.2行目から、ツリーに接続された2つの頂点がN−1行に与えられる.

しゅつりょく

1行目からN-1行目まで、各ノードの親ノード番号が2番目のノードから順次出力されます.

に答える

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<Integer> [] graph;
    static int[] parent;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        graph = new ArrayList[n + 1];
        visit = new boolean[n + 1];
        parent = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        StringTokenizer st;
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int to = Integer.parseInt(st.nextToken());
            int from = Integer.parseInt(st.nextToken());
            graph[to].add(from);
            graph[from].add(to);
        }

        dfs(1);
        for (int i = 2; i <= n; i++)
            System.out.println(parent[i]);
    }

    static void dfs(int start) {
        for (int child : graph[start]) {
            if (visit[child]) continue;
            parent[child] = start;
            visit[child] = true;
            dfs(child);
        }
    }

}

nの最大値は100000であるため、隣接行列を採用すると100000*100000となる.実行中にエラーが発生しました.
隣接リストで表現しましょう.

までうまく解決できなかったツリー巡り問題DFSもお馴染みになってきたので不思議に記録しましたが、ふふ