Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stack>
- using namespace std;
- const int n = 5;
- const int m = 5;
- int main()
- {
- int eptr[n];
- int idx[] = {0,2,4,7,9,10};
- int adj[] = {1,2,0,3,0,3,4,1,2,2};
- int par[n] = {0};
- int dfs[n];
- int low[n];
- for(int i=0; i<n; ++i)
- {
- dfs[i] = low[i] = n;
- eptr[i] = idx[i];
- }
- stack<int> s;
- s.push(0);
- low[0]=dfs[0]=0;
- int dfsnum = 0;
- int last = n;
- while(!s.empty())
- {
- int v = s.top();
- int u = adj[eptr[v]];
- //use this to check if you've just rolled back a step: lowpoints needed
- if(eptr[v] != idx[v] && v == par[adj[eptr[v]-1]])
- {
- if(low[adj[eptr[v]-1]] < low[v])
- low[v] = low[adj[eptr[v]-1]];
- }
- if(eptr[v] == idx[v+1])
- {
- s.pop();
- //check lp
- continue;
- }
- else if(dfs[u] == n)
- {
- s.push(u);
- par[u] = v;
- dfs[u] = ++dfsnum;
- }
- else if(dfs[u] < low[v] && u != par[v])
- {
- low[v] = dfs[u];
- }
- ++eptr[v];
- last = u;
- }
- for(int i=0; i<n; ++i)
- cout << "dfs " << dfs[i] << ", par " << par[i] << ", low " << low[i] << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement