groups.cpp

#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

bool check_conflict(set<string> &group, map<string, set<string> > &hates) {
    for(set<string>::iterator si = group.begin(); si != group.end(); ++si) {
        set<string> enemies = hates[*si];
        set<string> conflicts;
        set_intersection(group.begin(), group.end(),
                enemies.begin(), enemies.end(),
                inserter(conflicts, conflicts.begin()));
        if (conflicts.size() > 0) {
            return true;
        }
    }
    return false;
}

void remove_elements(set<string> &base, set<string> &to_remove) {
    for(set<string>::iterator si = to_remove.begin(); si != to_remove.end(); ++ si) {
        base.erase(*si);
    }
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        cout << "no input file\n";
        return 1;
    }

    ifstream input;
    input.open(argv[1]);
    if (!input) {
        cout << "cannot open file " << argv[1] << endl;
        return 1;
    }

    int testNum;
    input >> testNum;

    for(int i = 0; i < testNum; ++i) {
        int pairNum;

        string name1, name2;
        set<string> group1;
        set<string> group2;
        set<string> ungrouped;
        map<string, set<string> > hates;
        map<string, set<string> >::iterator mi;
        set<string>::iterator si;

        input >> pairNum;

        for(int j = 0; j < pairNum; ++j) {
            input >> name1 >> name2;
            if (hates.count(name1) == 0) {
                hates[name1] = set<string>();
            }
            hates[name1].insert(name2);
            if (hates.count(name2) == 0) {
                hates[name2] = set<string>();
            }
            hates[name2].insert(name1);
            ungrouped.insert(name1);
            ungrouped.insert(name2);
        }

        bool ok = true;
        while(ungrouped.size() > 0) {
            string name = *(ungrouped.begin());

            // add name to group1 and enemies to group2, enemies of group1 to group2 ...

            group1.insert(name);
            ungrouped.erase(name);
            group2.insert(hates[name].begin(), hates[name].end());
            remove_elements(ungrouped, hates[name]);

            while(true) {
                bool conflict = check_conflict(group1, hates) || check_conflict(group2, hates);
                if (conflict) {
                    ok = false;
                    break;
                }

                int size1 = group1.size();
                int size2 = group2.size();
                for(si = group2.begin(); si != group2.end(); ++si) {
                    group1.insert(hates[*si].begin(), hates[*si].end());
                    remove_elements(ungrouped, hates[*si]);
                }
                for(si = group1.begin(); si != group1.end(); ++si) {
                    group2.insert(hates[*si].begin(), hates[*si].end());
                    remove_elements(ungrouped, hates[*si]);
                }

                if (size1 == group1.size() && size2 == group2.size()) break;
            }

            if (ok == false) break;
        }

        cout << "Case #" << (i+1) << ": " << (ok ? "Yes" : "No") << endl;
    }
    return 0;
}