Maruf_Hasan

ArticulationBridgebyTanmoyvai

Jan 7th, 2020
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.53 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. #define pb push_back
  6. #define ll long long
  7. #define pii pair<int,int>
  8. #define pll pair<ll,ll>
  9. #define M 100007
  10. #define INF 1e9
  11. #define INFL 1e18
  12. #define PI acos(-1)
  13. #define mp make_pair
  14. #define fast_in_out ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  15.  
  16.  
  17.  
  18. vector<int>adj[M];
  19.  
  20.  
  21.  
  22. int parent[M];
  23. int low[M];
  24. int d[M];
  25. int visited[M];
  26. bool isArticulationPoint[M];
  27. int Time=0;
  28. bool mark[M];
  29. vector<pair<int,int> >ans;
  30. void DFS(int u)
  31. {
  32. Time=Time+1;
  33. visited[u]=1;
  34. d[u]=low[u]=Time;
  35. int noOfChildren=0;
  36. for(int i=0;i<adj[u].size();i++)
  37. {
  38. int v=adj[u][i];
  39. if(visited[v]==0)
  40. {
  41. parent[v]=u;
  42. DFS(v);
  43. low[u]=min(low[v],low[u]);
  44. if(low[v]>d[u])
  45. {
  46. ans.pb(mp(u,v));
  47. }
  48. }
  49. else if(v!=parent[u])
  50. {
  51. low[u]=min(d[v],low[u]);
  52. }
  53. }
  54. }
  55.  
  56.  
  57.  
  58.  
  59.  
  60. int main()
  61. {
  62. int n;
  63. cin>>n;
  64. int maxval=0;
  65. for(int i=0;i<n;i++)
  66. {
  67. int x,y;
  68. cin>>x>>y;
  69. adj[x].pb(y);
  70. adj[y].pb(x);
  71. maxval=max(maxval,max(x,y));
  72. }
  73. for(int i=0;i<=maxval;i++)
  74. {
  75. if(visited[i]==false)
  76. {
  77. // cout<<i<<endl;
  78. DFS(i);
  79. }
  80. }
  81. for(int i=0;i<ans.size();i++)
  82. {
  83. // if(isArticulationPoint[i])
  84. // cout<<i<<endl;
  85. cout<<ans[i].first<<" "<<ans[i].second<<endl;
  86. }
  87.  
  88. return 0;
  89. }
  90. //7
  91. //1 2
  92. //1 3
  93. //3 4
  94. //3 7
  95. //4 5
  96. //4 6
  97. //6 7
  98. //
Advertisement
Add Comment
Please, Sign In to add comment