Advertisement
SalmaYasser

Untitled

Oct 23rd, 2019
196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.30 KB | None | 0 0
  1.  
  2. There is an algorithm that can help find all the articulation points in a given graph by a single Depth First Search, that means with complexity , but it involves a new term called "Back Edge" which is explained below:
  3.  
  4. Given a DFS tree of a graph, a Back Edge is an edge that connects a vertex to a vertex that is discovered before it's parent. For example consider the graph given in Fig. 1. The figure given below depicts a DFS tree of the graph.
  5.  
  6. enter image description here
  7. In the above case, the edge 4 - 2 connects 4 to an ancestor of its parent i.e. 3, so it is a Back Edge. And similarly 3 - 1 is also a Back edge. But why bother about Back Edge? Presence of a back edge means presence of an alternative path in case the parent of the vertex is removed. Suppose a vertex is having a child such that none of the vertices in the subtree rooted at have a back edge to any vertex discovered before , that means if vertex is removed then there will be no path left for vertex or any of the vertices present in the subtree rooted at vertex v to reach any vertex discovered before , that implies, the subtree rooted at vertex will get disconnected from the entire graph, and thus the number of components will increase and will be counted as an articulation point. On the other hand, if the subtree rooted at vertex has a vertex that has back edge that connects it to a vertex discovered before , say , then there will be a path for any vertex in subtree rooted at to reach even after removal of , and if that is the case with all the children of , then will not count as an articulation point.
  8.  
  9. So ultimately it all converges down to finding a back edge for every vertex. So, for that apply a DFS and record the discovery time of every vertex and maintain for every vertex the earliest discovered vertex that can be reached from any of the vertices in the subtree rooted at . If a vertex is having a child such that the earliest discovered vertex that can be reached from the vertices in the subtree rooted at has a discovery time greater than or equal to , then does not have a back edge, and thus will be an articulation point.
  10.  
  11. So, till now the algorithm says that if all children of a vertex are having a back edge, then is not an articulation point. But what will happen when is root of the tree, as root does not have any ancestors. Well, it is very easy to check if the root is an articulation point or not. If root has more than one child than it is an articulation point otherwise it is not. Now how does that help?? Suppose root has two children, and . If there had been an edge between vertices in the subtree rooted at and those of the subtree rooted at , then they would have been a part of the same subtree.
  12.  
  13. Here's the pseudo code of the above algorithm:
  14.  
  15. class Solution {
  16. map<int,vector<int>> adjlist;
  17. int min_t=INT_MAX;
  18. int vis[100000]={0};
  19. int in[100000]={};
  20. int low_in[100000]={};
  21. int parent[100000]={};
  22. int t=1;
  23. vector<vector<int>> v;
  24. public:
  25. void dfs_helper(int node)
  26. {
  27. vis[node]=1;
  28. in[node]=t; low_in[node]=t; t++;
  29. for(auto neigh:adjlist[node])
  30. {
  31. parent[neigh]=node;
  32. if(vis[neigh]&&parent[node]!=neigh)
  33. low_in[node]=min(in[neigh],low_in[node]);
  34. else if(!vis[neigh])
  35. {
  36. dfs_helper(neigh);
  37. low_in[node]=min(low_in[node],low_in[neigh]);
  38. if(in[node]<low_in[neigh])
  39. v.push_back({node,neigh});
  40. }
  41. }
  42. }
  43.  
  44. vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
  45. for(int i=0;i<connections.size();i++)
  46. {
  47. adjlist[connections[i][0]].push_back(connections[i][1]);
  48. adjlist[connections[i][1]].push_back(connections[i][0]);
  49. }
  50. for(auto node: adjlist)
  51. {
  52. parent[node.first]=node.first;
  53. if(!vis[node.first])
  54. dfs_helper(node.first);
  55. }
  56. return v;
  57. }
  58. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement