# PBinfo #2354 – autostrada – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

În Iași a fost constituit grupul de sprijin “Împreună pentru A8”. Printre manifestările acestui grup este și o grevă în care trebuie să fie blocată o singură șosea din județ. Autoritățile județene vor să autorizeze aceste manifestări însă doar pe anumite șosele, astfel încât traficul să rămână posibil între oricare două localități.

Cerința
Cunoscând N numărul de localități din județ, acestea fiind codificate prin numere naturale din mulțimea 1, 2, …, N și M numărul de șosele care leagă direct câte două localități ale județului, să se afle K numărul de șosele pe care nu trebuie aprobate manifestările și care sunt aceste șosele. Fiecare șosea este determinată în mod unic de două numere naturale X și Y reprezentând cele două localități legate direct de șosea.

Date de intrare
Fișierul de intrare autostrada.in conține pe prima linie N M două numere naturale reprezentând numărul de localități din județ, respectiv numărul de șosele directe între perechi distincte de localități, iar pe următoarele M linii perechi de numere naturale X Y, reprezentând codurile localităților legate direct prin șosea.

Date de ieșire
Fișierul de ieșire autostrada.out va conține pe prima linie un singur număr natural K, reprezentând numărul de șosele pe care nu trebuie aprobate manifestații, iar pe următoarele K linii se află câte o pereche de numere X Y, reprezentând numerele de ordine ale localităților între care există șosea pe care nu trebuie autorizată greva. Perechile sunt afișate în ordine lexicografică.

Restricții și precizări

1 ≤ N ≤ 50
1 ≤ M ≤ 120
1 ≤ X, Y ≤ N
Perechea A B este mai mică lexicografic decât perechea C D dacă A < C sau A = C și B < D
Pentru datele de test există întotdeauna soluție
În concurs s-au acordat 10 puncte din oficiu; aici se acordă 10 puncte pentru testul din exemplu

Exemplu:
autostrada.in

6 7
1 2
2 4
1 4
3 4
3 5
5 6
3 6
autostrada.out

1
3 4
Explicație
Singura șosea pe care nu se poate autoriza greva este 3 4. Dacă eliminăm șoseaua 3 4 nu va fi posibil traficul între localitățile 1 3, 2 3 șamd.

## Cod sursă C++

```cpp
#include <fstream>
#include <cstring>
#include<algorithm>
#include<vector>
#define MAXN 101
using namespace std;
ifstream fin("autostrada.in");
ofstream fout("autostrada.out");
struct lista
{
    int nod;
    int c;
    lista *urm;
};
lista *g[MAXN];
struct Punct
{
    int x, y ;
    friend bool operator <(Punct p1, Punct p2)
    {
        if (p1.x != p2.x) return p1.x < p2.x ;
        else return p1.y < p2.y ;
    }
};
vector <Punct> v ;
int t[101],niv[101],l[101],viz[101],n,m;
void ad(int x,int y)
{
    lista *p;
    p=new lista;
    p->nod=y;
    p->c=0;
    p->urm=g[x];
    g[x]=p;
}
void citgraf()
{
    int x,y,k;
    fin>>n>>m;
    for(k=1; k<=m; k++)
    {
        fin>>x>>y;
        ad(x,y);
        ad(y,x);
    }
}
void df(int nod)
{
    lista *p;
    int x;
    viz[nod]=1;
    l[nod]=niv[nod];
    for(p=g[nod]; p; p=p->urm)
    {
        x=p->nod;
        if(!viz[x])
        {
            niv[x]=niv[nod]+1;
            t[x]=nod;
            df(x);
            if(l[nod]>l[x])
                l[nod]=l[x];
            if(l[x]>niv[nod])
                p->c=1;
        }
        else if(x!=t[nod]&&l[nod]>niv[x])
            l[nod]=niv[x];
    }
}
int main()
{
    int i,k=0;
    lista *p;
    Punct q ;
    citgraf();
    for(i=1; i<=n; i++)
        if(!viz[i])
        {
            niv[i]=1;
            df(i);
        }
    for(i=1; i<=n; i++)
        for(p=g[i]; p; p=p->urm)
            if(p->c==1)
                k++;
    fout<<k<<'\n';
    for(i=1; i<=n; i++)
        for(p=g[i]; p; p=p->urm)
            if(p->c==1)
            {
                if(i>p->nod) swap(i,p->nod);
                q.x=i;
                q.y=p->nod;
                v.push_back(q) ;
            }
    sort( v.begin() , v.end() , less<Punct>() ) ;
    for (i=0 ; i<k ; i++)
        fout<<v[i].x<<" "<<v[i].y<<"\n" ;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2354)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2354/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2354/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)