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
|
#include <filesystem>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
namespace {
using graph_type = map<int, set<int>>;
vector<int>
split_to_int(const string& line, const string& delimiters)
{
vector<int> result;
size_t start = 0;
size_t end = 0;
while ( (end = line.find_first_of(delimiters, start)) != string::npos ) {
if ( end != start ) {
result.emplace_back(stoi(line.substr(start, end - start)));
}
start = end + 1;
}
if ( start != line.size() ) {
result.emplace_back(stoi(line.substr(start)));
}
return result;
}
graph_type
read_lines(const filesystem::path& filename)
{
ifstream file{ filename };
graph_type result;
for ( string line; getline(file, line); ) {
auto parts = split_to_int(line, "<-> ,");
for ( size_t i = 1; i < parts.size(); ++i ) {
result[parts[0]].insert(parts[i]);
result[parts[i]].insert(parts[0]);
}
}
return result;
}
void
bfs_mark(const graph_type& graph, int start, set<int>& seen)
{
queue<int> queue;
queue.emplace(start);
seen.emplace(start);
while ( !queue.empty() ) {
int prg = queue.front();
queue.pop();
for ( auto link: graph.at(prg) ) {
if ( !seen.contains(link) ) {
queue.emplace(link);
seen.emplace(link);
}
}
}
}
void
part1(const graph_type& graph)
{
set<int> seen;
bfs_mark(graph, 0, seen);
cout << "Part1: " << seen.size() << '\n';
}
void
part2(const graph_type& graph)
{
set<int> seen;
int count = 0;
for ( const auto& [i, _]: graph ) {
if ( seen.contains(i) ) {
continue;
}
++count;
bfs_mark(graph, i, seen);
}
cout << "Part2: " << count << '\n';
}
} // namespace
int
main()
{
auto data = read_lines("data/day12.txt");
part1(data);
part2(data);
}
|
