Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cstdio>
- #include<vector>
- #define MAX_NODE 10000
- #define NIL 99999
- using namespace std;
- vector<bool> visited(MAX_NODE,false);
- vector<bool> Articulations_pont(MAX_NODE);
- vector<int> parent(MAX_NODE,-1);
- int time=0;
- vector<int> d(MAX_NODE,0);
- vector<int> low(MAX_NODE,0);
- vector<vector<bool>> articulation_bridge;
- void DFS_Visit(vector<vector<int>> gr, int u) // taking reference to see the changes in color
- {
- time++;
- d[u]=time;//cout<<"start time of "<<u<<" is "<<d[u]<<endl;
- low[u]=d[u];
- visited[u]=true;
- int num_of_childeren_visited=0;
- for(int i=0; i<gr[u].size(); i++)
- {
- int v=gr[u][i];
- bool flag = false;
- if(v==parent[u])
- {
- ///go to line (what??)
- flag = true;
- }
- if(!flag)
- {
- if(visited[v]==true)
- {
- low[u]=min(low[u],d[v]);
- }
- if(!visited[v])
- {
- parent[v]=u;
- DFS_Visit(gr,v);
- low[u]=min(low[u],low[v]);
- if(d[u]<low[v] && parent[u]!=-1)// when u is root, parent[u]=-1
- articulation_bridge[u][v]=true;
- num_of_childeren_visited++;
- }
- if(num_of_childeren_visited>=1 && parent[u]==-1)
- articulation_bridge[u][v]=true;
- }
- }//end for
- }
- void DFS(vector<vector<int>> gr)
- {
- int nv = gr.size() - 1;
- for(int i=1; i<=nv; i++)
- if(!visited[i])
- DFS_Visit(gr,i);
- }
- int main()
- {
- int n, e;
- scanf("%d %d", &n, &e);
- vector<vector<int>> gr;
- gr.clear();
- gr.resize(n+1);
- for(int i=0; i<e; i++)
- {
- int u,v;
- scanf("%d %d", &u, &v);
- gr[u].push_back(v);
- gr[v].push_back(u);
- }
- //for saving output
- articulation_bridge.resize(n+1);
- for(int i=0; i<n; i++)
- {
- articulation_bridge[i].resize(n);
- }
- DFS(gr);
- printf("Articulation bridges are :\n");
- for(int i=1; i<n+1; i++)
- for(int j=0; j<articulation_bridge[i].size(); j++)
- if(articulation_bridge[i][j])
- printf("%d------%d\n",i,j);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement