-
Notifications
You must be signed in to change notification settings - Fork 1
/
2009 J5-S3.cpp
186 lines (138 loc) · 4.86 KB
/
2009 J5-S3.cpp
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
/*
2009 J5/S3 - Degrees Of Separation
Difficulty: Medium
This question is not that difficult knowledge wise. It's just really annoying to implement.
General idea:
Implement the given graph
Add any friendships and delete friendships accordingly
The number of friends that person x has is the number of edges its node has on the graph
To determine the friends of friends, it suffices to iterate over each friend and add their friends to a set, this will ensure no duplicated are added
Lastly, to determine the degree of separation, perform a bfs since it will return minimum distance
*/
#include <iostream>
#include <vector>
#include <set>
#include <queue>
std::vector<std::set<int>> connections (50); //connections[i] is a set that contains all the people that are friends with person i
//Add friendships
void connect(int x, int y){
//Remember edges on the graph go both ways
connections[x].insert(y);
connections[y].insert(x);
}
//Delete friendships
void unfriend(int x, int y){
connections[x].erase(y);
connections[y].erase(x);
}
//Find total friends of friends
int friendsOfFriends(int x){
std::set<int> friends_of_friends; //Store the friends of friends
//For each friend of person x
for (auto it = connections[x].begin(); it != connections[x].end(); it++){
//For each friend's friend
for (auto it2 = connections[*it].begin(); it2 != connections[*it].end(); it2++){
//If the friend of a friend is not person x's friend and is not person x themselves, add friend of friend
if (connections[x].count(*it2) == 0 && *it2 != x){
friends_of_friends.insert(*it2);
}
}
}
//Since set has no duplicates, the size of the set will represent the total amount of friends of friends
return friends_of_friends.size();
}
//Find degree of seperation
int degreeOfSeperation(int x, int y){
std::queue<int> q; //Initialize queue
std::vector<bool> alreadyVisited (50, false); //Mark visited nodes on the graph
std::vector<int> distances (50); //distances[i] represents the degree of seperation between person x and person i
alreadyVisited[x] = true; //Mark person x as visited
q.push(x); //Get queue started
distances[x] = 0; //Mark person x distance as 0
while (!q.empty()){
int Friend = q.front();
q.pop();
//If node is target node
if (Friend == y){
return distances[Friend]; //return degree of separation if reachable
}
//For this persons friends
for (auto it = connections[Friend].begin(); it != connections[Friend].end(); it++){
if (!alreadyVisited[*it]){
q.push(*it);
distances[*it] = distances[Friend] + 1; //Degree of seperation is the previous nodes degree of separation + 1
}
alreadyVisited[*it] = true; //mark visited
}
}
return -1; //return -1 to indicate there's no path
}
int main(){
//Implement the given graph
connect(2, 6);
connect(1, 6);
connect(6, 7);
connect(6, 3);
connect(6, 4);
connect(6, 5);
connect(3, 4);
connect(4, 5);
connect(5, 3);
connect(3, 15);
connect(15, 13);
connect(13, 12);
connect(13, 14);
connect(7, 8);
connect(8, 9);
connect(9, 10);
connect(9, 12);
connect(10, 11);
connect(11, 12);
connect(16, 17);
connect(16, 18);
connect(17, 18);
//Take instructions until q
while (true){
char instruction;
int x, y;
std::cin >> instruction;
//If end
if (instruction == 'q'){
break;
}
//Connect
if (instruction == 'i'){
std::cin >> x >> y;
connect(x, y);
}
//Unfriend
if (instruction == 'd'){
std::cin >> x >> y;
unfriend(x, y);
}
//Number of friends
if (instruction == 'n'){
std::cin >> x;
std::cout << connections[x].size() << '\n'; //Count of all their node's edges
}
//Friends of friends
if (instruction == 'f'){
std::cin >> x;
int friendsfriends = friendsOfFriends(x);
std::cout << friendsfriends << '\n';
}
//Degree of separation
if (instruction == 's'){
std::cin >> x >> y;
int degree = degreeOfSeperation(x, y);
//-1 indicates no possible path
if (degree == -1){
std::cout << "Not connected" << '\n';
}
else{
std::cout << degree << '\n';
}
}
}
return 0;
}