Untitled
unknown
plain_text
a year ago
2.3 kB
3
Indexable
#include "scc.hpp" using namespace cs251; void scc:: tarjan(int node, std::vector<int> &disc, std::vector<int> &low, std::vector<int> &stack, std::vector<graph_vertex> &adj_list, std::vector<bool> &stack_member, int &answer){ static int time = 0; disc[node] = low[node] = ++time; stack.push_back(node); stack_member[node] = true; std :: cout << "Current Node = " << node << ", time = " << time << "\n"; for (int i = 0; i < adj_list[node].m_edges.size(); i++) { int v = adj_list[node].m_edges[i].m_destinationHandle; if(disc[v] == -1) { std :: cout << "Going to Node = " << v << "\n"; tarjan(v, disc, low, stack, adj_list, stack_member, answer); if (low[node] < low[v]) { std :: cout << "Changed coz disc[v] == -1, low[u] < low[v]\n"; low[node] = low[v]; } } else if (stack_member[v]) { if (low[node] < disc[v]) { std :: cout << "Changed coz stack_member[v], low[u] < disc[v]\n"; low[node] = disc[v]; } } } if (low[node] == disc[node]) { int x; std :: cout << "SCC Additioning : "; do { x = stack.back(); stack_member[x] = false; std :: cout << x << " "; stack.pop_back(); } while (stack.back() != node); std :: cout <<"\n"; answer++; } } int scc::search(const graph& g) { // TODO: implement search //throw std::logic_error("scc::" + std::string(__FUNCTION__) + "() not implemented"); int answer = 0; std:: vector <graph_vertex> adj_list = g.read_graph(); std:: vector<int> disc(g.graph_vertices, -1); std:: vector<int> low(g.graph_vertices, -1); std:: vector<bool> stack_member(g.graph_vertices, false); std:: vector<int> stack; for (int i=0; i < g.graph_vertices; i++) { if(disc[i] == -1) { // void tarjan(int node, std::vector<int> &disc, std::vector<int> &low, std::vector<int> &stack, std::vector<graph_vertex> &adj_list, std::vector<bool> &stack_member, int &answer); tarjan(i, disc, low, stack, adj_list, stack_member, answer); } } return answer; }
Editor is loading...
Leave a Comment