AOJの根付き木の表現問題をJavaで実装するとRunTimeErrorとなってしまう

Question

AOJで根付き木の表現問題（下記URL参照）をJavaで実装するとテストケース7で、RuntimeErrorとなってしまいます。
何が原因なのか分からなく、どこを直せばエラーにならなくなりますか？
また、今回のようなRuntimeErrorが出た場合の調査方法（ツールを使うなど）があれば教えていただきたいです。

Rooted Trees

import java.util.Scanner;

public class Main {
	private static int d[] = new int[100005];
	private static Node t[] = new Node[100005];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		for (int i = 0; i < n; i++) {
			t[i] = new Node();
		}

		int l = 0;
		for (int i = 0; i < n; i++) {
			int id = sc.nextInt();
			int k = sc.nextInt();
			for (int j = 0; j < k; j++) {
				int c = sc.nextInt();
				if (j == 0) {
					t[id].left = c;
				} else {
					t[l].right = c;
				}
				l = c;
				t[c].parent = id;
			}
		}

		int r = 0;
		for (int i = 0; i < n; i++) {
			if (t[i].parent == -1) r = i;
		}

		rec(r, 0);

		StringBuilder ans = new StringBuilder();
		for (int i = 0; i < n; i++) {
			ans.append("node ").append(Integer.toString(i)).append(": parent = ").append(Integer.toString(t[i].parent))
			.append( ", depth = ").append(Integer.toString(d[i])).append(", ");
			if (d[i] == 0) {
				ans.append("root, ");
			} else if (t[i].left == -1) {
				ans.append("leaf, ");
			} else {
				ans.append("internal node, ");
			}

			ans.append("[");
			int c = t[i].left;
			while (c != -1) {
				if (c != t[i].left) {
					ans.append(", ");
				}
				ans.append(Integer.toString(c));
				c = t[c].right;
			}
			ans.append("]\n");
		}

		System.out.print(ans.toString());

		sc.close();
	}

	private static void rec(int i, int p) {
		d[i] = p;
		if (t[i].left != -1) rec(t[i].left, p + 1);
		if (t[i].right != -1) rec(t[i].right, p);
	}

}

class Node {
	int parent;
	int left;
	int right;

	Node() {
		this.parent = -1;
		this.left = -1;
		this.right = -1;
	}
}

Answer 1

おそらくrecでスタックオーバーフローが起きてるんでしょう

大抵の場合大きなデータでないと起こらないのでツールを使ってもなかなか判断しづらいところです。
エラーメッセージやそれを起こすテストケースがわかるならそれを見れば一発ですが、わからない場合には再帰関数を使ってる部分に注意するぐらいしか方法はありません。

Comments

[ametyan]

ご回答ありがとうございます。ご指摘の通り、スタックオーバーフローが原因のようでした。
再帰ではなく、各ノードに対して深さを取得するよう修正したところ通りました。

private static int getDepth(int i) {
int d = 0;
while (t[i].parent != -1) {
i = t[i].parent;
d++;
}
return d;
}

[dodox86]

ちなみにテストケースは確認できるはずです。Last 100 Submissions(http://judge.u-aizu.ac.jp/onlinejudge/submission.jsp)で自分のRun# をクリックして出た画面で「テストケース」が出ます。テストケースをファイルでダウンロードして標準入力から入れれば、ローカルでデバッグ／テストできます。