2.8.6.cpp

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <cctype>

using namespace std;

int no_authors;

vector <string> get_names (const string& line);
void add_edges (vector <vector <int> > &G, const vector <string> &names, map <string, int> &DB);
vector <int> get_nodes (const vector <string> &names, map<string, int> &DB);
void add_edge (const int from, const int to, vector<vector<int> > &G);
vector<int> get_erdos_numbers (const vector<vector<int> > &G);

int main()
{
	int cases;
	cin >> cases;
	for (int i = 1; i <= cases; ++i)
	{
		int P, N;
		string line;
		map<string, int> DB;
		vector<vector<int> > G;

		// add "Erdos, P." to the databse
		no_authors = 1;
		DB["Erdos, P."] = 0;

		cin >> P >> N;

		// jump to the next line
		getline (cin, line);

		// read the database of papers
		for (; P; --P)
		{
			// read a paper
			getline (cin, line);
			// get a vector containing the authors of the paper
			vector<string> names = get_names (line);
			add_edges (G, names, DB);
		}

		/*
		// DEBUGING -------------------------------
		// print the resulting graph
		cout << "The size of the graph is " << G.size() << endl;
		for (int i = 0; i < G.size(); ++i)
		{
			for (auto it = DB.begin(); it != DB.end(); ++it)
				if (it->second == i)
					cout << it->first << ": ";

			for (int j = 0; j < G[i].size(); ++j)
				for (auto it = DB.begin(); it != DB.end(); ++it)
					if (it->second == G[i][j])
						cout << it->first << " | ";
			cout << endl;
		}
    	// ----------------------------------------
    	*/ 

		vector <int> erdos = get_erdos_numbers (G);
		cout << "Scenario " << i << endl;
		for (; N; --N)
		{
			getline (cin, line);
			if (DB.end() != DB.find(line) && erdos[ DB[line] ] >= 0)
				cout << line << ' ' << erdos[ DB[line] ] << endl;
			else
				cout << line << " infinity" << endl;
		}
	}

	return 0;
}

vector<int> get_erdos_numbers (const vector<vector<int> > &G)
{
	vector<int> erdos (no_authors);
	queue<int> bf_queue;

	// fill the matrix with -1 (infinity)
	fill (erdos.begin(), erdos.end(), -1);

	erdos[0] = 0;
	for (bf_queue.push(0); !bf_queue.empty(); bf_queue.pop())
	{
		int next = bf_queue.front();

		for (int i = 0; i < G[next].size(); ++i)
			if (erdos[ G[next][i] ] == -1)
			{
				erdos[ G[next][i] ] = erdos[next] + 1;
				bf_queue.push (G[next][i]);
			}
	}
    return erdos;
}

void add_edges (vector<vector<int> > &G, const vector<string> &names, map<string, int> &DB)
{
	vector<int> nodes = get_nodes (names, DB);

	/*
	// DEBUGING -------------------------------
	for (int i = 0; i < nodes.size(); ++i)
		cout << names[i] << ' ' << nodes[i] << " | ";
	cout << endl;
	// ----------------------------------------
	*/

	while (G.size() < no_authors) G.push_back (vector<int>());

	for (int i = 0; i < nodes.size(); ++i)
		for (int j = 0; j < nodes.size(); ++j)
			if (i != j) add_edge (nodes[i], nodes[j], G);
}

void add_edge (const int from, const int to, vector<vector<int> > &G)
{
	if (G[from].end() == find (G[from].begin(), G[from].end(), to))
		G[from].push_back (to);
}

vector <int> get_nodes (const vector <string> &names, map<string, int> &DB)
{
	vector<int> nodes;
	for (int i = 0; i < names.size(); ++i)
	{
		if (DB.end() == DB.find(names[i]))
			DB[names[i]] = no_authors++;
		nodes.push_back (DB[names[i]]);
	}
	return nodes;
}

vector <string> get_names (const string& line)
{
	vector <string> authors;
	for (int i = 0; i < line.size() && line[i] != ':';)
	{
		string author;
        while (isspace (line[i])) ++i;

        for (; line[i] != ':'; ++i)
		{
			author.push_back (line[i]);
			if (line[i] == '.' && line[i+1] == ',')
			{
				i += 2;
				break;
			}
		}
		authors.push_back (author);
	}

	return authors;
}