uvaSolutions/uva-10044.cpp at master · BryceShakeAir/uvaSolutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
//uva 10044
//Erdös Numbers

#include <iostream>
#include <climits>
#include <string>
#include <vector>
#include <string>
#include <queue>
#include <map>

using namespace std;

void BFS(vector <vector <int> > & Graph, int root, vector <int> & level);

int main(void)
{
	int T = 0, scenario = 0;
	cin >> T;
	while(T--){
		int p, n;
		cin >> p >> n;
		getchar();

		vector < vector <int> > Graph;
		map <string, int> name_code;
		map <int, string> code_name;
		int num_name = 0;

		for(int i = 0; i < p; ++i){
			string paper;
			int comma_counter = 0;
			vector <int> connected;
			getline(std::cin, paper);
			string author;

			for(int i = 0; i < paper.size(); ++i)
				if(paper[i] == ',' || paper[i] == ':'){
					++comma_counter;
					if(comma_counter % 2 == 0){
						if(name_code.find(author) == name_code.end()){
							vector <int> edges;
							Graph.push_back(edges);
							name_code[author] = num_name;
							code_name[num_name++] = author;
						}
						connected.push_back(name_code[author]);
						author.clear();
						++i;//skipping whitespace
					}
					else
						author += paper[i];

					if(paper[i] == ':')
						break;
				}
				else
					author += paper[i];

			for(int j = 0; j < connected.size(); ++j)
				for(int k = 0; k < connected.size(); ++k)
					if(k != j)
						Graph[connected[j]].push_back(connected[k]);
		}

		vector <int> level(Graph.size(), INT_MAX);
		BFS(Graph, name_code["Erdos, P."], level);

		++scenario;
		cout << "Scenario " << scenario << endl;

		for(int i = 0; i < n; ++i){
			string name;
			getline(std::cin, name);
			int result;

			if(name_code.find(name) == name_code.end())
				result = INT_MAX;
			else
				result = level[name_code[name]];
			if(result != INT_MAX)
				cout << name << ' ' << result << endl;
			else
				cout << name << ' ' << "infinity" << endl;
		}
	}
	return 0;
}

void BFS(vector <vector <int> > & Graph, int root, vector <int> & level)
{
	level[root] = 0;
	queue <int> Queue;
	Queue.push(root);

	while(!Queue.empty()){
		int front = Queue.front();
		Queue.pop();

		for(auto a : Graph[front])
			if(level[a] == INT_MAX){
				level[a] = level[front] + 1;
				Queue.push(a);
			}
	}
	return;
}