/ Published in: C++
Expand |
Embed | Plain Text
Copy this code and paste it in your HTML
// liarliar.cpp // 2011/1/2 #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(); }