Se știe că într-un graf neorientat conex, între oricare două vârfuri există cel putin un lanț iar lungimea unui lanț este egală cu numărul muchiilor care-l compun. Definim noțiunea lanț optim între două vârfuri X și Y ca fiind un lanț de lungime minimă care are ca extremități vârfurile X și Y. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe lanțuri optime, depinzând de configurația grafului.

Cerința

Fiind dat un graf neorientat conex cu N vârfuri etichetate cu numerele de ordine 1, 2, …, N și două vârfuri ale sale notate X și Y (1 ≤ X, Y ≤ N, X≠Y ), se cere să scrieți un program care determină vârfurile care aparțin tuturor lanțurilor optime dintre X și Y.

Date de intrare

Fișierul de intrare graf1.in conține pe prima linie patru numere naturale reprezentând: N (numărul de vârfuri ale grafului), M (numărul de muchii), X și Y (cu semnificația din enunț). Pe următoarele M linii câte două numere naturale nenule A[i], B[i] (1 ≤ A[i], B[i] ≤ N, A[i] ≠ B[i], pentru 1 ≤ i ≤ M ) fiecare dintre aceste perechi de numere reprezentând câte o muchie din graf.

Date de ieșire

Fișierul de ieșire graf1.out va conține pe prima linie, numărul de vârfuri comune tuturor lanțurilor optime dintre X și Y; pe a doua linie, numerele corespunzătoare etichetelor acestor vârfuri, dispuse în ordine crescătoare; între două numere consecutive de pe această linie se va afla câte un spațiu.

Restricții și precizări

2 ≤ N ≤ 7500
1 ≤ M ≤ 14000

Exemplul 1:

graf1.in

graf1.out

3
1 4 5

Exemplul 2:

graf1.in

3 2 1 3
1 2
3 1

graf1.out

2
1 3

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 graf1:

#include<fstream>
#include<vector>

using namespace std;

vector<int> L[7501];

int n, d[7501], viz[7501], x, y;
int dx[7501], dy[7501], a[7501], nod[7501], b[7501];

void Citire()
{
    int i, m, ii, jj;
    ifstream f("graf1.in");
    f >> n >> m >> x >> y;
    for (i = 1; i <= m; i++)
    {
        f >> ii >> jj;
        L[ii].push_back(jj);
        L[jj].push_back(ii);
    }
    f.close();
}

void BFS(int x, int *dx)
{
    int pr, ul, coada[7501], k, j ;
    unsigned int i ;
    for (j=1 ; j<=n ; j++) viz[j] = 0 ;
    pr = ul = 0 ;
    coada[0] = x ;
    dx[x] = 0 ;
    viz[x] = 1 ;
    while (pr <= ul)
    {
        k = coada[pr++] ;
        for (i=0 ; i<L[k].size() ; i++)
        {
            j = L[k][i] ;
            if (!viz[j])
            {
                viz[j] = 1 ;
                coada[++ul] = j ;
                dx[j] = 1 + dx[k] ;
            }
        }
    }
}

void Afisare()
{
    int i, minim ;
    minim = dx[y] ;
    for (i=1 ; i<=n ; i++)
        if (minim != dx[i] + dy[i])
            dx[i] = -1 ;
    for (i=1 ; i<=n ; i++)
        if (dx[i] != -1)
        {
            a[dx[i]]++ ;
            nod[dx[i]] = i ;
        }
    for (i=0 ; i<=n ; i++)
        if (a[i] == 1)
            b[nod[i]] = 1 ;
    int kk = 0 ;
    for (i=1 ; i<=n ; i++)
        if (b[i] == 1) kk++ ;
    ofstream fout("graf1.out") ;
    fout<<kk<<"\n" ;
    for (i=1 ; i<=n ; i++)
        if (b[i] == 1) fout<<i<<" " ;
    fout<<"\n" ;
    fout.close() ;
}

int main()
{
    Citire();
    BFS(x,dx);
    BFS(y,dy);
    Afisare();
    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 #2165 graf1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2165 graf1 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 #2165 graf1