一方通行（グラフ上の移動） Java編

　題意が上手くくみ取れずいったん放置。しかる後お手本を参考に。
　お手本では「幅優先探索の一種」ということでC++のQueueを使っていたが、どう見ても可変長な二重配列。

　Javaで再現するには……と悶々考えた結果、
「前の問題を活かそうぜ。そういう仕組みだろ」
　となり、隣接リストを利用する形になった。

「あ、グラフ理論ってそういうこと……」と漠然とした実用法が見えた気がする。するだけ。

コード

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();   //頂点の数

        ArrayList<Integer> visit = new ArrayList<Integer>();     //訪れた順番
        int[] done = new int[n];    //訪れたかどうかのチェック（boolでもいいかも）

        //ArrayListを二次元で作る（隣接リスト）
        ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<n; i++){
            ArrayList<Integer> gin = new ArrayList<Integer>();
            g.add(gin);
        }

        for(int i=0; i<n-1; i++){     //辺を取り込んでgに入れる
            int a = sc.nextInt();
            int b = sc.nextInt();
            a--;
            b--;
            g.get(a).add(b);
            g.get(b).add(a);
        }

        visit.add(0);    //最初は1（0）からスタートなので埋め込んでおく
        done[0] = 1;    //引数0（頂点1）は訪れた扱い

        while(visit.size() != n){     //処理していけばいずれvisitはNに辿り着く
            int now = visit.get(visit.size()-1);    //現在地はvisitの最後尾から取得
            for(int j=0; j<g.get(now).size(); j++){    //頂点によって辺は1つか2つ
                if(done[g.get(now).get(j)] == 0){     //頂点をdoneしていないなら
                    visit.add(g.get(now).get(j));     //visitの末尾に挿入して
                    done[g.get(now).get(j)] = 1;     //doneを1にする
                }
            }
        }

        for(int i=0; i<n; i++){
            System.out.println(visit.get(i)+1);
        }
    }
}