Advertisement
Guest User

Untitled

a guest
Jan 28th, 2015
175
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //============================================================================
  2. // Name        : Graf.cpp
  3. // Author      : Alexa Lukac
  4. // Version     :
  5. // Copyright   :
  6. // Description : Hello World in C++, Ansi-style
  7. //============================================================================
  8.  
  9. #include <iostream>
  10. using namespace std;
  11.  
  12. int n,m; //n-broj cvorova, m-broj grana
  13. int time1=0;
  14. bool connected[6000][6000];
  15. struct cvor
  16. {
  17.     cvor() : visited(false), disctime1(-1), endtime1(-1), low(-1) {}
  18.     bool visited;
  19.     int disctime1; //vreme pronalaska
  20.     int endtime1; //vreme zavrsetka sa ovim cvorom
  21.     int low; //najvise sto mozemo da odemo
  22. };
  23. cvor niz[5000];
  24.  
  25. void dfs(int a)
  26. {
  27.     if(niz[a].visited==false)
  28.     {
  29.         bool art=true;
  30.         cvor &t=niz[a];
  31.         t.visited=true;
  32.         t.low=t.disctime1=++time1;
  33.  
  34.         for(int i=0;i<n;i++)
  35.         {
  36.         if(connected[a][i]&&!niz[i].visited){
  37.             art=false;
  38.             bool most=true;
  39.             dfs(i);
  40.             if(niz[i].low>=t.disctime1)
  41.             {
  42.                 t.low=niz[i].low;
  43.                 most=false;
  44.             }else
  45.             {
  46.                 art=true;
  47.             }
  48.             if(most)
  49.                 cout << endl << "Most: " << a << "-" << i;
  50.         }
  51.         }
  52.         if(art)
  53.             cout << endl << "Artikulacioni cvor: " << a;
  54.         t.endtime1=++time1;
  55.         }
  56. }
  57.  
  58. int main() {
  59.     for(int i=0;i<5005;i++)
  60.         for(int j=0;j<5005;j++)
  61.             connected[i][j]=false;
  62.  
  63.     cin >> n >> m;
  64.  
  65.     for(int i=0;i<m;i++)
  66.     {
  67.         int a,b;
  68.         cin >> a >> b;
  69.         connected[a][b]=connected[b][a]=true;
  70.     }
  71.     return 0;
  72. }
  73.  
  74.  
  75. /*
  76.  * 4 4
  77. 0 1
  78. 1 2
  79. 1 3
  80. 0 3
  81.  
  82. 9 10
  83. 0 2
  84. 2 5
  85. 2 3
  86. 3 1
  87. 3 4
  88. 4 7
  89. 3 7
  90. 5 6
  91. 5 7
  92. 7 8
  93.  
  94.  *
  95.  */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement