Advertisement
keverman

Tarjan-Hopcroft algorithm

Feb 14th, 2018
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.98 KB | None | 0 0
  1. void articulationDFS(int u, int &time)
  2. {
  3.     int childrenCount = 0;
  4.     lowest[u] = discovery[u] = ++time;
  5.     visited[u] = true;
  6.  
  7.     for(auto v : adj[u])
  8.     {
  9.         if(!visited[v])
  10.         {
  11.             childrenCount++;
  12.             parent[v] = u;
  13.  
  14.             articulationDFS(v, time);
  15.  
  16.             lowest[u] = std::min(lowest[u], lowest[v]);
  17.  
  18.             if((parent[u] != -1 && lowest[v] >= discovery[u]) || (parent[u] == -1 && childrenCount > 1))
  19.                 AP[u] = true;
  20.         }
  21.  
  22.         else if(v != parent[u])
  23.             lowest[u] = std::min(lowest[u], discovery[v]);
  24.     }
  25. }
  26.  
  27. std::vector<int> findArticulationPoints()
  28. {
  29.     std::vector<int> articulationPoints;
  30.  
  31.     for(int i = 0; i < n; i++)
  32.     {
  33.         if(!visited[i])
  34.         {
  35.             int time = 0;
  36.             articulationDFS(i, time);
  37.         }
  38.     }
  39.  
  40.     for(int i = 0; i < n; i++)
  41.         if(AP[i])
  42.             articulationPoints.push_back(i);
  43.  
  44.     return articulationPoints;
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement