Untitled
unknown
c_cpp
2 years ago
6.0 kB
14
Indexable
#include <functional> #include <utility> #include <vector> #include <iostream> #include <queue> #include <unordered_map> #include <algorithm> #include <unordered_set> class Graph { public: using graph_type = std::vector<std::unordered_set<int> >; Graph() = default; Graph(int num_vertices) { g.resize(num_vertices); } Graph(const graph_type& g) : g(g) {}; Graph(graph_type&& g) : g(std::move(g)) {}; void AddEgde(int from, int to) { g[from].insert(to); } int NumVertices() const { return g.size(); } const std::unordered_set<int>& GetNeighbours(int v) const{ return g[v]; } ~Graph() = default; private: graph_type g; }; enum class Color { WHITE = 0, GRAY = 1, BLACK = 2 }; // bool HasCycle(const Graph& g, int v, std::vector<Color>& visited) { // visited[v] = Color::GRAY; // for (const auto& child: g.GetNeighbours(v)) { // if (visited[child] == Color::WHITE) { // HasCycle(g, child, visited); // } // if (visited[child] == Color::GRAY) { // return true; // } // } // visited[v] = Color::BLACK; // return false; // } // bool HasCycle(const Graph& g) { // size_t num_vertices = g.NumVertices(); // std::vector<Color> visited(num_vertices, Color::WHITE); // for (int i = 0; i < num_vertices; ++i) { // if (visited[i] == Color::WHITE) { // if (HasCycle(g, i, visited)) { // return true; // } // } // } // return false; // } // void DFS(const Graph& g, int v, std::vector<Color>& visited, std::vector<int>& sorted) { // visited[v] = Color::GRAY; // for (const auto& child: g.GetNeighbours(v)) { // if (visited[child] == Color::WHITE) { // DFS(g, child, visited, sorted); // } // } // sorted.push_back(v); // visited[v] = Color::BLACK; // } // std::vector<int> TopologicalSort(const Graph& g) { // if (HasCycle(g)) { // throw std::string("graph has cycle!"); // } // size_t num_vertices = g.NumVertices(); // std::vector<int> sorted; // sorted.reserve(num_vertices); // std::vector<Color> visited(num_vertices, Color::WHITE); // for (int i = 0; i < num_vertices; ++i) { // if (visited[i] == Color::WHITE) { // DFS(g, i, visited, sorted); // } // } // std::reverse(sorted.begin(), sorted.end()); // return sorted; // } void DFS(const Graph& g, int v, std::vector<Color>& visited, std::vector<int>& time_out) { visited[v] = Color::GRAY; for (const auto& child: g.GetNeighbours(v)) { if (visited[child] == Color::WHITE) { DFS(g, child, visited, time_out); } } visited[v] = Color::BLACK; time_out.push_back(v); } std::vector<int> DFS(const Graph& g) { size_t num_vertices = g.NumVertices(); std::vector<int> time_out; time_out.reserve(num_vertices); std::vector<Color> visited(num_vertices, Color::WHITE); for (int i = 0; i < num_vertices; ++i) { if (visited[i] == Color::WHITE) { DFS(g, i, visited, time_out); } } std::reverse(time_out.begin(), time_out.end()); return time_out; } Graph BuildInverted(const Graph& g) { size_t num_vertices = g.NumVertices(); Graph inverted(num_vertices); for (int i = 0; i < num_vertices; ++i) { for (const auto& v: g.GetNeighbours(i)) { inverted.AddEgde(v, i); } } return inverted; } void TraverseSCC(const Graph& g, int v, std::vector<Color>& visited, std::unordered_map<int, int>& SCC_indices, int strong_comp_num) { visited[v] = Color::GRAY; SCC_indices[v] = strong_comp_num; for (const auto& child: g.GetNeighbours(v)) { if (visited[child] == Color::WHITE) { TraverseSCC(g, child, visited, SCC_indices, strong_comp_num); } } visited[v] = Color::BLACK; } std::pair<std::unordered_map<int, int>, int> FindSCC(const Graph& g) { size_t num_vertices = g.NumVertices(); std::unordered_map<int, int> SCC_index(num_vertices); std::vector<int> time_out = DFS(g); std::vector<Color> visited(num_vertices, Color::WHITE); Graph inverted = BuildInverted(g); int strong_comp_num = 0; for (const auto& v: time_out) { if (visited[v] == Color::WHITE) { TraverseSCC(inverted, v, visited, SCC_index, strong_comp_num); ++strong_comp_num; } } return std::make_pair(SCC_index, strong_comp_num); } Graph GraphCondensation(const Graph& g) { size_t num_vertices = g.NumVertices(); const auto& [SCC_index, strong_comp_num] = FindSCC(g); Graph condensed_graph(strong_comp_num); for (int from = 0; from < num_vertices; ++from) { for (const auto& to: g.GetNeighbours(from)) { if (SCC_index.at(to) != SCC_index.at(from)) { condensed_graph.AddEgde(SCC_index.at(from), SCC_index.at(to)); } } } return condensed_graph; } /* 7 9 0 1 1 3 2 0 3 2 3 4 1 4 4 5 5 6 6 4 */ int main() { int n; std::cin >> n; int m; std::cin >> m; Graph g(n); for (int i = 0; i < m; ++i) { int from, to; std::cin >> from >> to; g.AddEgde(from, to); } const auto& [SCC_index, strong_comp_num] = FindSCC(g); std::cout << strong_comp_num << std::endl; for (const auto& [v, idx]: SCC_index) { std::cout << "v: " << v << " idx: " << idx << std::endl; } auto condensed_graph = GraphCondensation(g); for (int from = 0; from < condensed_graph.NumVertices(); ++from) { std::cout << "from: " << from <<" to:"; for (const auto& to: condensed_graph.GetNeighbours(from)) { std::cout << to <<" "; } std::cout << std::endl; } return 0; }
Editor is loading...