Advertisement
Guest User

Untitled

a guest
Jan 28th, 2015
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int n,m; //n-broj cvorova, m-broj grana
  5. int time1=0;
  6. bool connected[6000][6000];
  7. struct cvor
  8. {
  9.     cvor() : visited(false), disctime1(-1), endtime1(-1), low(-1) {}
  10.     bool visited;
  11.     int disctime1; //vreme pronalaska
  12.     int endtime1; //vreme zavrsetka sa ovim cvorom
  13.     int low; //najvise sto mozemo da odemo
  14. };
  15. cvor niz[5000];
  16.  
  17. void dfs(int a)
  18. {
  19.     if(niz[a].visited==false)
  20.     {
  21.         bool art=true;
  22.         cvor &t=niz[a];
  23.         t.visited=true;
  24.         t.low=t.disctime1=++time1;
  25.  
  26.         for(int i=0;i<n && connected[a][i] && !niz[i].visited;i++)
  27.         {
  28.             art=false;
  29.             bool most=true;
  30.             dfs(i);
  31.             if(niz[i].low>=t.disctime1)
  32.             {
  33.                 t.low=niz[i].low;
  34.                 most=false;
  35.             }else
  36.             {
  37.                 art=true;
  38.             }
  39.             if(most)
  40.                 cout << endl << "Most: " << a << "-" << i;
  41.         }
  42.         if(art)
  43.             cout << endl << "Artikulacioni cvor: " << a;
  44.         t.endtime1=++time1;
  45.         }
  46. }
  47.  
  48. int main() {
  49.     for(int i=0;i<5005;i++)
  50.         for(int j=0;j<5005;j++)
  51.             connected[i][j]=false;
  52.  
  53.     cin >> n >> m;
  54.  
  55.     for(int i=0;i<m;i++)
  56.     {
  57.         int a,b;
  58.         cin >> a >> b;
  59.         connected[a][b]=connected[b][a]=true;
  60.     }
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement