/* * Forced Games (via mjd@cs.auckland.ac.nz) */ #include #include #include #include using namespace std; typedef vector NLIST; // node (neighbor) list typedef vector< NLIST > ADJLIST; // graph data structure class Game { public: ADJLIST adj; NLIST status; // who can win or draw at vertex (1, 2 or 3) NLIST player; // who owns vertex (1 or 2) // creators + destroyers // Game(int n = 0) : adj(n), status(n), player(n) {} ~Game() {} // stream I/0 // friend ostream& operator<<(ostream&, const Game&); friend istream& operator>>(istream&, Game&); bool setPlayers(); // returns false if not bipartite void setStatus(); // if connected + bipartite this should be fine. // mutators // bool addEdge(int u, int v) // false if already exists { if ( isEdge(u,v) ) return false; adj[u].push_back(v); return true; } // accessors // int order() const // number of vertices { return adj.size(); } bool isEdge(int u, int v) const { int n = order(); assert(u >= 0 && u < n); assert(v >= 0 && v < n); assert(u != v); for (int i=0; i>(istream& in, Game& G) { char line[LLEN]; int n; //in >> n; in.getline(line, LLEN); istringstream lineIn(line); lineIn >> n; // cerr << "n = " << n << '\n'; G.adj.resize(n); G.status.resize(n); G.player.resize(n); for (int i=0; i>v2) { // cerr << "v2 = " << v2 << '\n'; if (v2 == -1) { G.player[v1] = 2; G.status[v1] = 1; break; } else if (v2 == -2) { G.player[v1] = 1; G.status[v1] = 2; break; } else if (v2 == -3) { G.status[v1] = 3; break; } else G.addEdge(v1,v2); } } in.getline(line, LLEN); // get trailing blank line return in; } int main() { Game G; while (true) { cin >> G; int n = G.order(); if (n==0) break; //cerr << G; if (! G.setPlayers() ) { cout << "Not bipartite\n\n"; continue; } //cerr << G; G.setStatus(); //cerr << G; for (int i=0; i