Î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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema autostrada:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2354 autostrada

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2354 autostrada de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2354 autostrada