-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathP280.cpp
66 lines (64 loc) · 1.37 KB
/
P280.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
#include <iostream>
#include <vector>
#include <set>
#include <stack>
int main() {
std::vector<int> neighbours[100];
while(true) {
int n;
std::cin >> n;
if(n == 0)
return 0;
// build graph:
for(int i = 0; i < n; ++i) {
neighbours[i].clear();
}
while(true) {
int a;
std::cin >> a;
if(a == 0)
break;
while(true) {
int b;
std::cin >> b;
if(b == 0)
break;
neighbours[a-1].push_back(b-1);
}
}
// handle queries:
int numQueries;
std::cin >> numQueries;
std::set<int> unreachable;
for(int ignore = 0; ignore < numQueries; ++ignore) {
int q;
std::cin >> q; // query
--q;
//std::cerr << (q+1) << " -> ";
unreachable.clear();
for(int i = 0; i < n; ++i) {
unreachable.insert(i);
}
std::stack<int> s;
s.push(q);
while(!s.empty()) {
int p = s.top();
s.pop();
for(unsigned int i = 0; i < neighbours[p].size(); ++i) {
int p2 = neighbours[p][i];
if(unreachable.find(p2) != unreachable.end()) {
//std::cerr << (p2+1) << " ";
unreachable.erase(p2);
s.push(p2);
}
}
}
//std::cerr << std::endl;
std::cout << unreachable.size();
for(std::set<int>::const_iterator it = unreachable.begin(); it != unreachable.end(); ++it) {
std::cout << " " << (*it + 1);
}
std::cout << std::endl;
}
}
}