AOJ 2619: Thread Tree

はじめに

• 問題: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2619
• 解答: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1362752
• Javaで実装

問題訳

ネイサン・O・デイビスは、JAGチャンネルという電子掲示板を運営していた。 彼は、この電子掲示板にスレッドビューを追加したいと思った。

他の掲示板と同じように、JAGチャンネルもスレッド形式になっている。 スレッド（トピックとも呼ばれる）とは、一つの話題を取り扱う複数の投稿の集まりである。 投稿は、新しいスレッドを作成するか、スレッドにある投稿にリプライする形で投稿できる。

スレッドビューは木構造のようなビューで、返信の構造を可視化したものである。 それぞれの投稿は木のノードで、サブノードとして、その投稿へのリプライを 古いものから順番に持つ。

例えば、あるユーザが'hoge'と投稿した。 他のユーザが、それに'fuga'とリプライした。 さらに他のユーザが'hoge'に対して'piyo'とリプライした。 'fuga'に対して、'foobar', 'jagjag' とリプライされた。 この場合の木構造は以下の通りである。

（原文の図参照）

実装を簡単にするために、ネイサンは簡単な形式を考えた。 それぞれの投稿の深さをドットで表す。 リプライはその親の投稿よりも1つドットが多くなる。 先ほどの木構造をこの形式で表すと以下のようになる。

（原文の図参照）

あなたには、このように、1つのスレッドを木構造を表示するプログラムを書いてもらいたい

入力

一番最初の行の整数 はこのスレッドの投稿の数である。 それぞれの投稿は2行で表される。 1行目は整数 であり、 これは、番目の投稿は 番目の投稿へのリプライであることを表している。 2行目は文字列 で、これは投稿の内容である。 は常に0で、これはどの投稿にもリプライしていないことを表す。 この投稿が最初の投稿である。

投稿の内容は1文字以上50文字以下で、英数字の列である。

出力

問題文に示したような図を出力せよ

実装

• 木構造を実装すれば良いが、子ノードは順番を持つことに注意。
• ハッシュでノードを管理し、リプライ先が取得できるようにする。
• 最終的に再帰的にprintしていく

class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        HashMap<Integer, Node> map = new HashMap<Integer, Node>();
        Node root = null;
                
        for (int i = 1; i <= n; i++) {
            int k = Integer.parseInt(br.readLine());
            String m = br.readLine();
            Node node = new Node(m);
            
            // 親を持つ場合その親の子に追加
            if(k != 0){
                Node parent = map.get(k);
                parent.addChild(node);
                node.depth = parent.depth + 1;
            }else{
                root = node;
                node.depth = 0;
            }
            
            map.put(i, node);
        }
        root.print();
    }
}


class Node{
    ArrayList<Node> children = new ArrayList<Node>();
    String message;
    int depth;
    Node(String message){
        this.message = message;
    }
    public void addChild(Node n){
        children.add(n);
    }
    // 再帰的print
    public void print(){
        StringBuffer buf = new StringBuffer();
        for(int i = 0; i < depth; i++)
            buf.append('.');
        buf.append(message);
        System.out.println(buf.toString());
        
        for(int i = 0; i < children.size(); i++)
            children.get(i).print();
    }
}

余談

Sample Input がラブライブだったりする