Advertisement
HmHimu

arti

Jul 20th, 2017
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.90 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //int matrix[100][100];
  5.  
  6. list<int> adj[100];
  7. char clr[100];
  8. int d[100];
  9. int f[100];
  10. int prev[100];
  11. int t,v;
  12. int low[100];
  13. vector<int> point;
  14.  
  15. void visit_dfs(int u)
  16. {
  17. clr[u]='g';
  18. t=t+1;
  19. d[u]=t;
  20. low[u]=d[u];
  21. int n=0;
  22. for(list<int>::iterator it=adj[u].begin();it!=adj[u].end();it++)
  23. {
  24. if(clr[*it]=='w')
  25. {
  26. n++;
  27. prev[*it]=u;
  28. visit_dfs(*it);
  29.  
  30. low[u]=min(low[u],low[*it]);
  31.  
  32. if(prev[u]==-1 && n>1)
  33. {
  34. point.push_back(u);
  35. }
  36.  
  37. if (low[*it] >= d[u] && prev[u]!=-1)
  38. {
  39. point.push_back(u);
  40. }
  41.  
  42.  
  43. }
  44. else if(*it != prev[u])
  45. {
  46. low[u]=min(low[u],d[*it]);
  47. }
  48. }
  49. /*for(int i=1;i<=v;i++)
  50. {
  51. if(matrix[u][i]==1 && clr[i]=='w')
  52. {
  53. prev[i]=u;
  54. visit_dfs(i);
  55. }
  56. }*/
  57.  
  58. clr[u]='b';
  59. t=t+1;
  60. f[u]=t;
  61. }
  62.  
  63. void dfs()
  64. {
  65. for(int i=1;i<=v;i++)
  66. {
  67. clr[i]='w';
  68. prev[i]=-1;
  69. f[i]=10000000;
  70. d[i]=10000000;
  71. low[i]=1000000;
  72. }
  73.  
  74. t=0;
  75.  
  76. for(int i=1;i<=v;i++)
  77. {
  78. if(clr[i]=='w')
  79. {
  80. visit_dfs(i);
  81. }
  82. }
  83. }
  84.  
  85.  
  86. int main()
  87. {
  88. int a,b,k=1;
  89. cout<<"Enter number of Vartex : ";
  90. cin>>v;
  91. while(1)
  92. {
  93. cout<<"Edge "<<k<<" : ";
  94. cin>>a>>b;
  95.  
  96. if(a>v || b>v)
  97. {
  98. cout<<"Wrong input"<<endl;
  99. }
  100. else if(a==0 && b==0)
  101. {
  102. break;
  103. }
  104. else
  105. {
  106. adj[a].push_back(b);
  107. adj[b].push_back(a);
  108. k++;
  109. }
  110. }
  111.  
  112. dfs();
  113.  
  114. for(int i=0;i<point.size();i++)
  115. {
  116. cout<<point[i]<<" ";
  117. }
  118.  
  119. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement