AOJ1305 WA

gistfile1.cpp

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

using namespace std;

class Solver {
public:
	vector<vector<int> > members;
	Solver(vector<vector<int> >& members) : members(members) {}

	set<int> res_;
	set<int> visited_;

	void count(int idx) {
		if (visited_.count(idx)) return;
		visited_.insert(idx);
		if (idx < members.size()) {
			for (int i = 0; i < members[idx].size(); ++i) {
				count(members[idx][i]);
			}
		} else {
			res_.insert(idx);
		}
		return;
	}

	int solve() {
		count(0);
		return res_.size();
	}
};

int main()
{
	int n;
	while ((cin>>n), n) {
		vector<string> membersStr(n);
		{ string _; getline(cin, _); }
		for (int i = 0; i < n; ++i) {
			getline(cin, membersStr[i]);
		}

		map<string, int> idxs;
		for (int i = 0; i < n; ++i) {
			const string group = membersStr[i].substr(0, membersStr[i].find(":"));
			idxs[group] = idxs.size();
		}

		vector<vector<int> > members(n);
		for (int i = 0; i < n; ++i) {
			string cur = membersStr[i].substr(membersStr[i].find(":") + 1);
			cur = cur.substr(0, cur.size() - 1);
			while (!cur.empty()) {
				int pos = cur.find(",");

				string member;
				if (pos == string::npos) {
					member = cur;
					cur.clear();
				} else {
					member = cur.substr(0, pos);
					cur = cur.substr(pos + 1);
				}
				if (idxs.count(member)) {
					members[i].push_back(idxs[member]);
				} else {
					members[i].push_back(idxs[member] = idxs.size());
				}
			}
		}

		/*for (int i = 0; i < members.size(); ++i) {
			cout<<i<<":";
			for (int j = 0; j < members[i].size(); ++j) {
				cout<<members[i][j]<<",";
			}
			cout<<endl;
		}*/

		Solver solver(members);
		cout<<solver.solve()<<endl;
	}

	return 0;
}