68 lines
1.4 KiB
C++
68 lines
1.4 KiB
C++
|
#include <iostream>
|
||
|
|
#include <vector>
|
||
|
|
#include <fstream>
|
||
|
|
#include <unordered_map>
|
||
|
|
#include <set>
|
||
|
|
|
||
|
|
#include <tuple>
|
||
|
|
|
||
|
|
typedef std::unordered_multimap<char, char> graph_type;
|
||
|
|
|
||
|
|
std::tuple<graph_type, std::set<char>> build_graph()
|
||
|
|
{
|
||
|
|
graph_type graph;
|
||
|
|
std::ifstream file("Day7.in");
|
||
|
|
std::string line;
|
||
|
|
|
||
|
|
std::set<char> nodes;
|
||
|
|
|
||
|
|
while (std::getline(file, line)) {
|
||
|
|
char a = line[5];
|
||
|
|
char b = line[36];
|
||
|
|
std::cout << "a: " << a << ", b:" << b << std::endl;
|
||
|
|
|
||
|
|
graph.insert({ b, a });
|
||
|
|
|
||
|
|
nodes.insert(a);
|
||
|
|
nodes.insert(b);
|
||
|
|
}
|
||
|
|
|
||
|
|
return std::make_tuple(graph, nodes);
|
||
|
|
}
|
||
|
|
|
||
|
|
bool node_blocked(graph_type &graph, std::set<char> &to_consider, char node)
|
||
|
|
{
|
||
|
|
auto [start, end] = graph.equal_range(node);
|
||
|
|
for (auto pair = start; pair != end; ++pair) {
|
||
|
|
char parent = pair->second;
|
||
|
|
if (to_consider.count(parent) > 0) {
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
int main(int argc, char **argv)
|
||
|
|
{
|
||
|
|
auto [graph, to_consider] = build_graph();
|
||
|
|
|
||
|
|
std::vector<char> order;
|
||
|
|
while (!to_consider.empty()) {
|
||
|
|
for (auto node = to_consider.begin(); node != to_consider.end(); ++node) {
|
||
|
|
bool blocked = node_blocked(graph, to_consider, *node);
|
||
|
|
if (blocked)
|
||
|
|
continue;
|
||
|
|
|
||
|
|
order.push_back(*node);
|
||
|
|
std::cout << *node;
|
||
|
|
|
||
|
|
to_consider.erase(node);
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
std::cout << std::endl;
|
||
|
|
|
||
|
|
return 0;
|
||
|
|
}
|