/*
 * main.cpp
 *
 *  Created on: 2011/1/24
 *      Author: dirk
 */

#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <string>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>

// we use bundled property here
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> Graph;

typedef std::pair<size_t, size_t> Edge;
typedef std::map<std::string, size_t> NameVertexMap;
typedef std::vector<Edge> EdgeArray;

template <typename DistanceMap>
class bacon_number_recorder : public boost::default_bfs_visitor {
public:
	bacon_number_recorder(DistanceMap d) : _d(d) {}

	// overloading tree_edge function
	template <typename Edge, typename Graph>
	void tree_edge(Edge e, const Graph &g) const {
		typename Graph::vertex_descriptor u = boost::source(e, g), v = boost::target(e, g);
		_d[v] = _d[u] + 1;
	}

private:
	DistanceMap _d;
};

template <typename DistanceMap>
static bacon_number_recorder<DistanceMap> record_bacon_number(DistanceMap d) {
	return bacon_number_recorder<DistanceMap>(d);
}

int main(int argc, char **argv) {
	// preparing the data
	std::ifstream fin(argv[1]);
	if(!fin) {
		std::cerr << "Can't open data file, leaving...\n";
		return EXIT_FAILURE;
	}

	// reading the file
	int i_no_chunks(0), i_no_accused(0);
	NameVertexMap nvm_members;
	NameVertexMap::iterator nvm_it;
	bool b_inserted;
	std::string str_accuser, str_accused;
	EdgeArray edge_array;
	size_t max_id(0), u(0), v(0);

	fin >> i_no_chunks;
	edge_array.reserve(i_no_chunks * 5);
	for(int i = 0; i < i_no_chunks; ++i) {
		fin >> str_accuser >> i_no_accused;

		boost::tie(nvm_it, b_inserted) = nvm_members.insert(std::make_pair(str_accuser, max_id));
		if(b_inserted) {
			u = max_id;
			++max_id;
		} else {
			u = nvm_it->second;
		}

		for(int j = 0; j < i_no_accused; ++j) {
			fin >> str_accused;

			boost::tie(nvm_it, b_inserted) = nvm_members.insert(std::make_pair(str_accused, max_id));
			if(b_inserted) {
				v = max_id;
				++max_id;
			} else {
				v = nvm_it->second;
			}
			edge_array.push_back(std::make_pair(u,v));
		}
	}
	Graph graph(&edge_array[0], &edge_array[edge_array.size()-1], nvm_members.size());

	// processing the data
	std::vector<int> bacon_number(boost::num_vertices(graph), 0);
	bacon_number[0] = 0;
	boost::breadth_first_search(graph, 0, boost::visitor(record_bacon_number(&bacon_number[0])));

	// output the results
	int i_groups[2] = {0,0};
	Graph::vertex_iterator i, end;
	for(boost::tie(i, end) = boost::vertices(graph); i != end; ++i) {
		++i_groups[bacon_number[*i]%2];
	}

	if(i_groups[0]>i_groups[1]) {
		std::cout << i_groups[0] << ' ' << i_groups[1] << '\n';
	} else {
		std::cout << i_groups[1] << ' ' << i_groups[0] << '\n';
	}
}

/*
 * main.cpp
 *
 *  Created on: 2011/1/24
 *      Author: dirk
 */

#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <string>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/graphviz.hpp>

// we use bundled property here
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
	// vertex property
	boost::property<boost::vertex_name_t, std::string> > Graph;

typedef std::pair<size_t, size_t> Edge;
typedef std::map<std::string, size_t> NameVertexMap;
typedef std::vector<Edge> EdgeArray;

template <typename DistanceMap>
class bacon_number_recorder : public boost::default_bfs_visitor {
public:
	bacon_number_recorder(DistanceMap d) : _d(d) {}

	// overloading tree_edge function
	template <typename Edge, typename Graph>
	void tree_edge(Edge e, const Graph &g) const {
		typename Graph::vertex_descriptor u = boost::source(e, g), v = boost::target(e, g);
		_d[v] = _d[u] + 1;
	}

private:
	DistanceMap _d;
};

template <typename DistanceMap>
static bacon_number_recorder<DistanceMap> record_bacon_number(DistanceMap d) {
	return bacon_number_recorder<DistanceMap>(d);
}

int main(int argc, char **argv) {
	// preparing the data
	std::ifstream fin(argv[1]);
	if(!fin) {
		std::cerr << "Can't open data file, leaving...\n";
		return EXIT_FAILURE;
	}

	// reading the file
	int i_no_chunks(0), i_no_accused(0);
	NameVertexMap nvm_members;
	NameVertexMap::iterator nvm_it;
	bool b_inserted;
	std::string str_accuser, str_accused;
	EdgeArray edge_array;
	size_t max_id(0), u(0), v(0);

	fin >> i_no_chunks;
	edge_array.reserve(i_no_chunks * 5);
	for(int i = 0; i < i_no_chunks; ++i) {
		fin >> str_accuser >> i_no_accused;

		boost::tie(nvm_it, b_inserted) = nvm_members.insert(std::make_pair(str_accuser, max_id));
		if(b_inserted) {
			u = max_id;
			++max_id;
		} else {
			u = nvm_it->second;
		}

		for(int j = 0; j < i_no_accused; ++j) {
			fin >> str_accused;

			boost::tie(nvm_it, b_inserted) = nvm_members.insert(std::make_pair(str_accused, max_id));
			if(b_inserted) {
				v = max_id;
				++max_id;
			} else {
				v = nvm_it->second;
			}
			edge_array.push_back(std::make_pair(u,v));
		}
	}
	Graph graph(&edge_array[0], &edge_array[edge_array.size()-1], nvm_members.size());

	// processing the data
	std::vector<int> bacon_number(boost::num_vertices(graph), 0);
	bacon_number[0] = 0;
	boost::breadth_first_search(graph, 0, boost::visitor(record_bacon_number(&bacon_number[0])));

	// output the results
	int i_groups[2] = {0,0};
	Graph::vertex_iterator i, end;
	for(boost::tie(i, end) = boost::vertices(graph); i != end; ++i) {
		++i_groups[bacon_number[*i]%2];
	}

	if(i_groups[0]>i_groups[1]) {
		std::cout << i_groups[0] << ' ' << i_groups[1] << '\n';
	} else {
		std::cout << i_groups[1] << ' ' << i_groups[0] << '\n';
	}

}

liarliar version B (using boost::graph, based on Kevin Bacon example)

C++