// liarliar.cpp
// 2011/1/2
// [email protected]

#include <fstream>
#include <string>
#include <iostream>
#include <vector>
#include <set>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;

class Liar {
private:
	typedef vector<string> Names;
	typedef set<string> Set;

	class Group {
	public:
		Set &TheSet() {return the_set;}
		Set const &TheSet() const {return the_set;}
		Group *const TheOppositeSet() {return the_opposite_set;}
		Group const *const TheOppositeSet() const {return the_opposite_set;}
		void SetOppositeSet(Group *const p) {the_opposite_set = p;}
	private:
		Set the_set;
		Group * the_opposite_set;
	};

	typedef list<Group> Groups;

public:
	Liar();

	int Readin(string const file_name);
	int Process();
	void Output() const;
private:
	int get_a_chunk(ifstream & fin, string & accuser, int & no_liars, Names & liars);
	int process_a_chunk(string const & accuser, Names const & liars);

private:
	Groups _groups;
	int _g1, _g2;
};

int Liar::process_a_chunk(string const & accuser, Names const & liars) {
	Groups::iterator it_g;
	Set::iterator it_s;
	Names::const_iterator it_n;
	for(it_g = _groups.begin(); it_g != _groups.end(); ++it_g) {
		if((it_s = it_g->TheSet().find(accuser)) != it_g->TheSet().end()) { // found
			it_g->TheSet().insert(accuser);
			it_g->TheOppositeSet()->TheSet().insert(liars.begin(), liars.end());
			return 0; // end of task
		}
		else { // let's now try all the names in liars
			for(it_n = liars.begin(); it_n != liars.end(); ++it_n) {
				if((it_s = it_g->TheSet().find(*it_n)) != it_g->TheSet().end()) { // found
					it_g->TheSet().insert(liars.begin(), liars.end());
					it_g->TheOppositeSet()->TheSet().insert(accuser);
					return 0;
				}
			}
		}
	}

	// not found, we create 2 groups here
	Groups::iterator it_g1, it_g2;
	it_g1 = _groups.insert(_groups.end(), Group());
	it_g2 = _groups.insert(_groups.end(), Group());
	it_g1->TheSet().insert(accuser);
	it_g1->SetOppositeSet(&*it_g2);
	it_g2->TheSet().insert(liars.begin(), liars.end());
	it_g2->SetOppositeSet(&*it_g1);
	return 0;
}

Liar::Liar() {}

int Liar::Readin(string const file_name) {
	if(!_groups.empty()) _groups.clear();

	ifstream fin(file_name.c_str());
	int no_chunk(0);
	fin >> no_chunk;

	string accuser;
	int no_liars(0);
	Names * pliars = new Names[no_chunk];
	for(int i = 0; i < no_chunk; ++i) {
		get_a_chunk(fin, accuser, no_liars, pliars[i]);
		process_a_chunk(accuser, pliars[i]);
	}
	delete [] pliars;

	/*Groups::const_iterator it_g;
	for(it_g = _groups.begin(); it_g != _groups.end(); ++it_g) {
		copy(it_g->TheSet().begin(), it_g->TheSet().end(), ostream_iterator<string>(cout, " "));
		cout << '\n';
	}*/
	return 0;
}

int Liar::Process() { // we merge all data in this function
	_g1 = _g2 = 0;
	if(_groups.size() == 2) {
		_g1 = _groups.begin()->TheSet().size();
		_g2 = _groups.begin()->TheOppositeSet()->TheSet().size();
		return 0;
	}
	Groups::iterator it_g1, it_g2;
	vector<bool> merged(_groups.size(), false);
	int i1(0), i2(0);
	for(it_g1 = _groups.begin(); it_g1 != _groups.end(); ++it_g1) {
		for(it_g2 = _groups.begin(); it_g2 != _groups.end(); ++it_g2) {
			i2 = 0;
			if(it_g1 != it_g2 && it_g1->TheOppositeSet() != &*it_g2 && !merged[i2]) {
				// try if we can merge this group into the it_g1 group
				if(search(it_g1->TheSet().begin(), it_g1->TheSet().end(), it_g2->TheSet().begin(), it_g2->TheSet().end())!=it_g1->TheSet().end()) { //found
					it_g1->TheSet().insert(it_g2->TheSet().begin(), it_g2->TheSet().end());
					it_g1->TheOppositeSet()->TheSet().insert(it_g2->TheOppositeSet()->TheSet().begin(), it_g2->TheOppositeSet()->TheSet().end());
					merged[i2] = true;
					if(!(i2 % 2)) merged[i2 + 1] = true;
					else merged[i2 - 1] = true;
				}
			}
			++i2;
		}
		++i1;
	}

	/*Groups::const_iterator it_g;
	for(it_g = _groups.begin(); it_g != _groups.end(); ++it_g) {
		copy(it_g->TheSet().begin(), it_g->TheSet().end(), ostream_iterator<string>(cout, " "));
		cout << '\n';
	}*/

	Groups::const_iterator it_cg = _groups.begin();
	for(size_t i = 0; i < _groups.size(); i+=2) {
		if(merged[i] != false) {
			_g1 = it_cg->TheSet().size();
			it_cg++;
			_g2 = it_cg->TheSet().size();
			break;
		}
		it_cg++;
		it_cg++;
	}

	return 0;
}

void Liar::Output() const {
	if(_g1 > _g2) cout << _g1 << ' ' << _g2 << '\n';
	else cout << _g2 << ' ' << _g1 << '\n';
}

int Liar::get_a_chunk(ifstream &fin, string &accuser, int &no_liars, Names &liars) {
	fin >> accuser >> no_liars;
	string liar;
	for(int i = 1; i <= no_liars; ++i) {
		fin >> liar;
		liars.push_back(liar);
	}
	return 0;
}

int main(int argc, char **argv) {
	Liar liar;
	liar.Readin(argv[1]);
	liar.Process();
	liar.Output();
}

liarliar version A (using std::set)

C++