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
| #include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std;
class Ssc{ public: void Tarjan(int); Ssc(int n_, vector<vector<int>> &g) : n(n_) { graph = g; dfn = vector<int>(n,0); low = vector<int>(n,0); scc = vector<bool>(n,false); time = 0; sscnum = 0; } vector<vector<int>> Sscs; vector<vector<int>> graph; int n; vector<int> dfn; vector<int> low; vector<bool> scc; int time, sscnum; stack<int> stk; };
void Ssc::Tarjan(int root) { if( dfn[root] ) return; dfn[root] = low[root] = ++time; stk.push(root); scc[root] = true; for(int v = 0;v < n;v++) { if(!dfn[v] && graph[root][v]) { Tarjan(v); low[root] = min(low[root], low[v]); } else if(scc[v] && graph[root][v]) { low[root] = min(low[root], dfn[v]); } }
if(low[root] == dfn[root]) { sscnum ++; vector<int> sc; while(true) { int x = stk.top(); scc[x] = false; stk.pop(); sc.push_back(x); if(x == root) break; } Sscs.push_back(sc); } }
int main() { vector<vector<int>> graph = { {0,1,1,0,0,0}, {0,0,0,1,0,0}, {0,0,0,1,1,0}, {1,0,0,0,0,1}, {0,0,0,0,0,1}, {0,0,0,0,0,0}, }; Ssc S(6, graph); S.Tarjan(0); int index = 1; for(auto i : S.Sscs) { cout << "SSC (" << index++ << ") : "; for(auto j : i) { cout << j << " "; } cout << endl; } cout << "The Number of SSC : " << S.sscnum << endl; return 0; }
|