山傘のプログラミング勉強日記[Java & Unity]

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[Aizu Online Judge] Rooted Trees (ALDS1_7_A: Rooted Trees)

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

8.2 根付き木の表現

本当にA問題なのかと疑いたくなります。

根付き木はデータ構造の一部です。あまり理解できませんでしたが、頭に入れておきたいです。

問題

根付き木 | アルゴリズムとデータ構造 | Aizu Online Judge

深さを再帰で求めようとしたらスタックオーバフローが起きたので、while文で求めるとうまくいきました。

コード

import java.util.Scanner;

public class ALDS1_7_A1 {
    static final int NIL = -1;
    static final int MAX = 100005;
    static Node[] T = new Node[MAX];
    static int n;
    static int D[] = new int[MAX];

    public static void main(String[] args) {
        int i, j, d, v, c, l = 0;
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();

        for(i = 0; i < n; i++) {
            T[i] = new Node(NIL, NIL, NIL);
        }
        for(i = 0; i < n; i++) {
            v = scan.nextInt();
            d = scan.nextInt();
            for(j = 0; j < d; j++) {
                c = scan.nextInt();
                if(j == 0) {
                    T[v].setL(c);
                }else {
                    T[l].setR(c);
                }
                l = c;
                T[c].setP(v);
            }
        }
        scan.close();

        for(i = 0; i < n; i++) {
            D[i] = getDepth(i);
        }


        for(i = 0; i < n; i++) {
            disp(i);
        }
    }
    // 深さを求める
    static int getDepth(int u) {
        int d = 0;
        while(T[u].getP() != NIL) {
            u = T[u].getP();
            d ++;
        }
        return d;
    }
    static void disp(int u) {
        int i, c;
        System.out.print("node " + u + ": ");
        System.out.print("parent = " + T[u].getP() + ", ");
        System.out.print("depth = " + D[u] + ", ");
        if(T[u].getP() == NIL) {
            System.out.print("root, ");
        }else if(T[u].getL() == NIL) {
            System.out.print("leaf, ");
        }else {
            System.out.print("internal node, ");
        }
        System.out.print("[");
        for(i = 0, c = T[u].getL(); c != NIL; i++, c = T[c].getR()) {
            if(i != 0) {
                System.out.print(", ");
            }
            System.out.print(c);
        }
        System.out.println("]");
    }
}

class Node {
    private int p, l ,r;
    public Node(int p, int l, int r) {
        this.p = p;
        this.l = l;
        this.r = r;
    }
    int getP() {
        return p;
    }
    int getL() {
        return l;
    }
    int getR() {
        return r;
    }
    void setR(int r) {
        this.r = r;
    }
    void setL(int l) {
        this.l = l;
    }
    void setP(int p) {
        this.p = p;
    }
}