Advertisement
Masfiq_ds_algo

ALGR: Articulation Bridge

Apr 29th, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.22 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<vector>
  4. #define MAX_NODE 10000
  5. #define NIL 99999
  6. using namespace std;
  7.  
  8. vector<bool> visited(MAX_NODE,false);
  9. vector<bool> Articulations_pont(MAX_NODE);
  10. vector<int> parent(MAX_NODE,-1);
  11. int time=0;
  12. vector<int> d(MAX_NODE,0);
  13. vector<int> low(MAX_NODE,0);
  14.  
  15. vector<vector<bool>> articulation_bridge;
  16.  
  17. void DFS_Visit(vector<vector<int>> gr, int u) // taking reference to see the changes in color
  18. {
  19.     time++;
  20.     d[u]=time;//cout<<"start time of "<<u<<" is "<<d[u]<<endl;
  21.     low[u]=d[u];
  22.     visited[u]=true;
  23.     int num_of_childeren_visited=0;
  24.     for(int i=0; i<gr[u].size(); i++)
  25.     {
  26.         int v=gr[u][i];
  27.         bool flag = false;
  28.         if(v==parent[u])
  29.         {
  30.             ///go to line (what??)
  31.             flag = true;
  32.         }
  33.         if(!flag)
  34.         {
  35.             if(visited[v]==true)
  36.             {
  37.                 low[u]=min(low[u],d[v]);
  38.             }
  39.             if(!visited[v])
  40.             {
  41.                 parent[v]=u;
  42.                 DFS_Visit(gr,v);
  43.                 low[u]=min(low[u],low[v]);
  44.  
  45.                 if(d[u]<low[v] && parent[u]!=-1)// when u is root, parent[u]=-1
  46.                     articulation_bridge[u][v]=true;
  47.                 num_of_childeren_visited++;
  48.             }
  49.             if(num_of_childeren_visited>=1 && parent[u]==-1)
  50.                 articulation_bridge[u][v]=true;
  51.         }
  52.     }//end for
  53. }
  54. void DFS(vector<vector<int>> gr)
  55. {
  56.     int nv = gr.size() - 1;
  57.     for(int i=1; i<=nv; i++)
  58.         if(!visited[i])
  59.             DFS_Visit(gr,i);
  60. }
  61.  
  62. int main()
  63. {
  64.     int n, e;
  65.     scanf("%d %d", &n, &e);
  66.     vector<vector<int>> gr;
  67.     gr.clear();
  68.     gr.resize(n+1);
  69.     for(int i=0; i<e; i++)
  70.     {
  71.         int u,v;
  72.         scanf("%d %d", &u, &v);
  73.         gr[u].push_back(v);
  74.         gr[v].push_back(u);
  75.     }
  76.     //for saving output
  77.     articulation_bridge.resize(n+1);
  78.     for(int i=0; i<n; i++)
  79.     {
  80.         articulation_bridge[i].resize(n);
  81.     }
  82.     DFS(gr);
  83.     printf("Articulation bridges are :\n");
  84.     for(int i=1; i<n+1; i++)
  85.         for(int j=0; j<articulation_bridge[i].size(); j++)
  86.             if(articulation_bridge[i][j])
  87.                 printf("%d------%d\n",i,j);
  88.     return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement