Advertisement
DrMikeMorgan

Iterative Lowpoint Algorithm Implementation

Oct 30th, 2014
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include <iostream>
  2. #include <stack>
  3.  
  4.  
  5. using namespace std;
  6. const int n = 5;
  7. const int m = 5;
  8.  
  9. int main()
  10. {
  11.     int eptr[n];
  12.     int idx[] = {0,2,4,7,9,10};
  13.     int adj[] = {1,2,0,3,0,3,4,1,2,2};
  14.  
  15.     int par[n] = {0};
  16.     int dfs[n];
  17.     int low[n];
  18.  
  19.  
  20.  
  21.     for(int i=0; i<n; ++i)
  22.     {
  23.         dfs[i] = low[i] = n;
  24.         eptr[i] = idx[i];
  25.     }
  26.  
  27.     stack<int> s;
  28.     s.push(0);
  29.     low[0]=dfs[0]=0;
  30.     int dfsnum = 0;
  31.     int last = n;
  32.     while(!s.empty())
  33.     {
  34.         int v = s.top();
  35.         int u = adj[eptr[v]];
  36.  
  37.         //use this to check if you've just rolled back a step: lowpoints needed
  38.  
  39.         if(eptr[v] != idx[v] && v == par[adj[eptr[v]-1]])
  40.         {
  41.             if(low[adj[eptr[v]-1]] < low[v])
  42.                 low[v] = low[adj[eptr[v]-1]];
  43.         }
  44.         if(eptr[v] == idx[v+1])
  45.         {
  46.             s.pop();
  47.             //check lp
  48.             continue;
  49.         }
  50.         else if(dfs[u] == n)
  51.         {
  52.             s.push(u);
  53.             par[u] = v;
  54.             dfs[u] = ++dfsnum;
  55.         }
  56.         else if(dfs[u] < low[v] && u != par[v])
  57.         {
  58.             low[v] = dfs[u];
  59.         }
  60.         ++eptr[v];
  61.         last = u;
  62.     }
  63.  
  64.     for(int i=0; i<n; ++i)
  65.         cout << "dfs " << dfs[i] << ", par " << par[i] << ", low " << low[i] << "\n";
  66.  
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement