nicuvlad76

Untitled

Nov 5th, 2022
933
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. #include <algorithm>
  4. #define N 105
  5. using namespace std;
  6.  
  7. ifstream fin("autostrada.in");
  8. ofstream fout("autostrada.out");
  9.  
  10. struct lista
  11. {
  12.     int nod, c;
  13.     lista *urm;
  14. }*g[N];
  15.  
  16. struct Punct
  17. {
  18.     int x,y;
  19.     friend bool operator <(Punct p1, Punct p2)
  20.     {
  21.         if(p1.x!=p2.x)return p1.x<p2.x;
  22.         else return p1.y<p2.y;
  23.     }
  24. };
  25. vector <Punct> v;
  26. void add(int x, int y)
  27. {
  28.     lista*p=new lista;
  29.     p->nod=y;
  30.     p->c=0;
  31.     p->urm=g[x];
  32.     g[x]=p;
  33. }
  34. int n,m;
  35. void citire()
  36. {
  37.     int x,y,k;
  38.     fin>>n>>m;
  39.     for(k=1;k<=m;++k)
  40.     {
  41.         fin>>x>>y;
  42.         add(x,y);
  43.         add(y,x);
  44.     }
  45. }
  46. int t[N], viz[N], niv[N], l[N];
  47. void DFS(int nod)
  48. {
  49.     lista *p;
  50.     int x;
  51.     viz[nod]=1;
  52.     l[nod]=niv[nod];
  53.     for(p=g[nod];p; p=p->urm)
  54.     {
  55.         x=p->nod;
  56.         if(!viz[x])
  57.         {
  58.             niv[x]=niv[nod]+1;
  59.             t[x]=nod;
  60.             DFS(x);
  61.             if(l[nod]>l[x])l[nod]=l[x];
  62.             if(l[x]>niv[nod])p->c=1;
  63.         }
  64.         else
  65.             if(x!=t[nod] && l[nod]>niv[x])
  66.              l[nod]=niv[x];
  67.     }
  68. }
  69. int main()
  70. {
  71.   lista *p;
  72.   citire();
  73.   Punct q;
  74.   for(int i=1;i<=n;i++)
  75.     if(!viz[i])
  76.   {
  77.       niv[i]=1;
  78.       DFS(i);
  79.   }
  80.   int k=0;
  81.   for(int i=1;i<=n;i++)
  82.     for(p=g[i]; p; p=p->urm)
  83.      if(p->c==1) k++;
  84.   fout<<k<<"\n";
  85.   for(int i=1;i<=n;i++)
  86.     for(p=g[i];p;p=p->urm)
  87.      if(p->c==1)
  88.   {
  89.       if(i>p->nod)swap(i,p->nod);
  90.       q.x=i;
  91.       q.y=p->nod;
  92.       v.push_back(q);
  93.   }
  94.   sort(v.begin(), v.end(),less<Punct>());
  95.   for(int i=0;i<k;i++)
  96.     fout<<v[i].x<<" "<<v[i].y<<"\n";
  97.   return 0;
  98. }
  99.  
Advertisement
Add Comment
Please, Sign In to add comment