UVa 12168 - Cat vs. Dog

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

class MaximumCardinalityBipartiteMatching {
private:
	vector<bool> visited;
	vector<vector<int> > edges;
	vector<int> owner;

	bool isThereAnAugmentingPathFrom(int leftNode) {
		if (visited[leftNode])
			return false;
		visited[leftNode] = true;
		for (int i = 0; i < edges[leftNode].size(); i++) {
			int rightNode = edges[leftNode][i];
			if (owner[rightNode] == -1 || isThereAnAugmentingPathFrom(owner[rightNode])) {
				owner[rightNode] = leftNode;
				return true;
			}
		}
		return false;
	}
public:
	// p_edges is the adjacency matrix, e.g. {{0, 1, 2}, {}, {1, 4, 5}}
	// nodes on the left are numbered from 0 to edges.size()-1
	// nodes on the right are numbered from 0 to numberOfVerticesOnTheRight
	// the adjacency matrix contains only directed edges from left to right set
	int getMaximumCardinality(const vector<vector<int> > & p_edges, int numberOfVerticesOnTheRight) {
		edges = p_edges;
		owner.assign(numberOfVerticesOnTheRight, -1);
		int cardinality = 0;
		for (int leftNode = 0; leftNode < edges.size(); leftNode++) {
			visited.assign(edges.size(), false);
			if (isThereAnAugmentingPathFrom(leftNode)) {
				cardinality++;
			}
		}
		return cardinality;
	}
};

int main() {

	int cases;
	scanf("%d", &cases);
	for (; cases; cases--) {
		int cats, dogs, numberOfVoters;
		scanf("%d %d %d", &cats, &dogs, &numberOfVoters);
		char voter[numberOfVoters][2][5];
		vector<vector<int> > edges;
		int catLoverCount = 0, dogLoverCount = 0;
		int id[numberOfVoters];

		for (int v = 0; v < numberOfVoters; v++) {
			scanf("%s %s", voter[v][0], voter[v][1]);
			bool catLover = voter[v][0][0] == 'C' || voter[v][0][0] == 'c';
			if (catLover) {
				id[v] = catLoverCount++;
				vector<int> emptyVector;
				edges.push_back(emptyVector);
			} else {
				id[v] = dogLoverCount++;
			}
			for (int j = 0; j < v; j++) {
				if (strcmp(voter[j][0], voter[v][1]) == 0 || strcmp(voter[j][1], voter[v][0]) == 0) {
					if (catLover)
						edges[id[v]].push_back(id[j]);
					else
						edges[id[j]].push_back(id[v]);
				}
			}
		}

		MaximumCardinalityBipartiteMatching mcbm;
		int disatifiedVoters = mcbm.getMaximumCardinality(edges, dogLoverCount);
		printf("%d\n", numberOfVoters - disatifiedVoters);
	}

	return 0;
}