Codeforces #52 (div2) C "Corporation Mail"

問題：http://codeforces.com/contest/56/problem/C

参加形式：本番

ヒエラルキー構造の雇用関係を表す文字列が与えられる．この構文規則は木構造を表しており，またそれぞれのノードの要素は名前で表現されている．ある名前をルートとしたときの部分木に同じ名前が複数含まれていることがある．このような名前の数の合計を求める．

文字列を頭から見て行って，コロンならば部分木の始まりとしてスタックにプッシュして以下の文字列の部分木における親ノードとし，ピリオドならばその直前が名前で表されている場合はスタックに積んである親ノードの番号を記録，直前が名前でない（ピリオドである）場合は部分木の終了としてスタックから親ノードをポップする．各ノードに記録されたルートノードまでの親ノードのうち，自分自身と同じ名前のノードの数を合計する．若干コードが汚い．

コード

import java.util.*;

public class C_CorporationMail {
	public static void main(String[] args) {
		char[] cs = new Scanner(System.in).nextLine().toCharArray();
		Deque<Integer> q = new ArrayDeque<Integer>();
		List<String> names = new ArrayList<String>();
		List<Integer> parents = new ArrayList<Integer>();
		int v = 0;
		q.push(v);
		++v;
		String name = "";
		for (int i = 0; i < cs.length; ++i) {
			char c = cs[i];
			if (Character.isUpperCase(c)) {
				name += cs[i];
			} else if (c == '.') {
				if (!name.isEmpty()) {
					names.add(name);
					parents.add(q.getFirst());
					++v;
				} else {
					q.pop();
				}
				name = "";
			} else if (c == ':') {
				names.add(name);
				parents.add(q.getFirst());
				q.push(v);
				name = "";
				++v;
			}
		}
		int count = 0;
		for (int i = 0; i < names.size(); ++i) {
			name = names.get(i);
			for (int p = parents.get(i) - 1; p != -1; p = parents.get(p) - 1) {
				if (names.get(p).equals(name)) {
					++count;
				}
			}
		}
		System.out.println(count);
	}
}