fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Graph {
  5. public:
  6. 	int n, m;
  7. 	bool isDirected;
  8.  
  9.     vector<vector<int>> adj;
  10.  
  11.     Graph(int nodes, bool isDigraph): adj(nodes){
  12.         n = nodes;
  13.         m = 0;
  14.         isDirected = isDigraph;
  15.     }
  16.  
  17.     void insertEdge(int u, int v){
  18.     	if(u >=n || v >=n || u < 0 || v < 0){
  19.     		cout<<"Either of the vertices doesn't exists!!\n"
  20.     		"please enter vertices within range of [0,"<<n<<").\n";
  21.     		return;
  22.     	}
  23.  
  24.     	if(isDirected || u != v)
  25.     		adj[u].push_back(v);
  26.  
  27.         if(!isDirected && u != v)
  28.         	adj[v].push_back(u);
  29.     }
  30.  
  31.     void findCutEdgesAndVertices() {
  32.  
  33.     	vector<bool> visited(n);
  34.  
  35. 	    vector<bool> cutVertices(n);
  36. 	    vector<vector<int>> cutEdges;
  37.  
  38. 	    vector<int> discovery(n), low(n);
  39.  
  40. 	    int timer = 0;
  41.  
  42.         // Calling with root node of DFS with 0, parent -1 since it has no parent.
  43.         // You can call with any node in the graph as root.
  44.         dfsTraversal(0, -1, timer, visited, cutVertices, cutEdges, discovery, low);
  45.  
  46.         cout<<"The cut vertices(Articulation Points) in the graph are:,\n";
  47.         for(int i=0; i<n; ++i){
  48.             if(cutVertices[i])
  49.                 cout<<i<<" ";
  50.         }
  51.         cout<<"\n";
  52.  
  53.         cout<<"The cut edges(Bridges) in the graph are:,\n";
  54.         for(auto edge: cutEdges){
  55.                 cout<<edge[0]<<" -> "<<edge[1]<<"\n";
  56.         }
  57.         cout<<"\n";
  58.     }
  59.  
  60.     void dfsTraversal(int u, int parent, int &timer, vector<bool> &visited, 
  61.     		vector<bool> &cutVertices, vector<vector<int>> &cutEdges, 
  62.     		vector<int> &discovery, vector<int> &low){
  63.  
  64.         visited[u] = true;
  65.         low[u] = discovery[u] = ++timer;
  66.  
  67.         int children = 0; //Useful for root node in DFS tree.
  68.  
  69.         for(auto v: adj[u]){
  70.             if(!visited[v]){
  71.  
  72.                 ++children;
  73.  
  74.                 dfsTraversal(v, u, timer, visited, cutVertices, cutEdges, discovery, low);
  75.  
  76.                 low[u] = min(low[u], low[v]);
  77.  
  78.                 // If discovery of current node(u) is less than finish of any of its neighbour nodes,
  79.                 // then it means neighbour(v) has not found any route to another node which is discovered
  80.                 // before current node(u). Hence, a cut edge.
  81.                 if(discovery[u] < low[v])
  82.                     cutEdges.push_back({u, v});
  83.  
  84.                 // This is root node of dfs tree with more than 1 child, i.e cutVertex
  85.                 if(parent == -1 && children > 1)
  86.                     cutVertices[u] = true;
  87.  
  88.                 // This is starting point of cycle if found, i.e cutVertex
  89.                 else if(parent != -1 && discovery[u] <= low[v])
  90.                     cutVertices[u] = true;
  91.  
  92.             }
  93.             else if(v != parent){
  94.                 low[u] = min(low[u], low[v]);
  95.             }
  96.         }
  97.     }
  98. };
  99.  
  100.  
  101. int main(){
  102.  
  103. 	int n, di, m;
  104. 	cin>>n>>di>>m;
  105.  
  106. 	Graph g(n, di);
  107.  
  108. 	int u, v;
  109.  
  110. 	for(int i = 0; i < m; ++i){
  111. 		cin>>u>>v;
  112. 		g.insertEdge(u, v);
  113. 	}
  114.  
  115. 	g.findCutEdgesAndVertices();
  116.  
  117. 	return 0;
  118. }
  119.  
  120.  
Success #stdin #stdout 0s 4500KB
comments (?)
stdin
copy 
7 0 7
0 1
0 2
1 3
2 3
2 5
5 6
3 4
stdout
copy 
The cut vertices(Articulation Points) in the graph are:,
2 3 5 
The cut edges(Bridges) in the graph are:,
5 -> 6
2 -> 5
3 -> 4
https://ideone.com/wGSJ7W
Cut vertices and cut edges using discovery and minimum finish timestamps || Time complexity: O(V E)
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!