Go to the documentation of this file.00001 #include "scc.h"
00002 #include <algorithm>
00003 #include <vector>
00004 using namespace std;
00005
00006 vector<vector<int> > SCC::get_result() {
00007 int node_count = graph.size();
00008 dfs_numbers.resize(node_count, -1);
00009 dfs_minima.resize(node_count, -1);
00010 stack_indices.resize(node_count, -1);
00011 stack.reserve(node_count);
00012 current_dfs_number = 0;
00013
00014 for(int i = 0; i < node_count; i++)
00015 if(dfs_numbers[i] == -1)
00016 dfs(i);
00017
00018 reverse(sccs.begin(), sccs.end());
00019 return sccs;
00020 }
00021
00022 void SCC::dfs(int vertex) {
00023 int vertex_dfs_number = current_dfs_number++;
00024 dfs_numbers[vertex] = dfs_minima[vertex] = vertex_dfs_number;
00025 stack_indices[vertex] = stack.size();
00026 stack.push_back(vertex);
00027
00028 const vector<int> &successors = graph[vertex];
00029 for(int i = 0; i < successors.size(); i++) {
00030 int succ = successors[i];
00031 int succ_dfs_number = dfs_numbers[succ];
00032 if(succ_dfs_number == -1) {
00033 dfs(succ);
00034 dfs_minima[vertex] = min(dfs_minima[vertex], dfs_minima[succ]);
00035 } else if(succ_dfs_number < vertex_dfs_number && stack_indices[succ] != -1) {
00036 dfs_minima[vertex] = min(dfs_minima[vertex], succ_dfs_number);
00037 }
00038 }
00039
00040 if(dfs_minima[vertex] == vertex_dfs_number) {
00041 int stack_index = stack_indices[vertex];
00042 vector<int> scc;
00043 for(int i = stack_index; i < stack.size(); i++) {
00044 scc.push_back(stack[i]);
00045 stack_indices[stack[i]] = -1;
00046 }
00047 stack.erase(stack.begin() + stack_index, stack.end());
00048 sccs.push_back(scc);
00049 }
00050 }
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093