Cerinţa

Se dă lista muchiilor unui graf neorientat și două vârfuri p q . Să se determine cel mai scurt lanț cu extremitățile p q.

Date de intrare

Fişierul de intrare lantminim.in conţine pe prima linie numerele n p q, reprezentând numărul de vârfuri ale grafului și cele două vârfuri date. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire lantminim.out va conţine pe prima linie numărul de vârfuri din lanțul determinat. A doua linie va conține vârfurile din acest lanț, separate prin exact un spațiu.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• în fișierul de intrare muchiile se pot repeta;
• orice lanț de lungime minimă cu extremitățile p q este acceptat;
• pentru toate datele de test există cel puțin un lanț de la p la q;

Exemplu

lantminim.in

6 2 6
1 2
1 3
1 4
3 4
4 5
4 6
5 6

lantminim.out

4
2 1 4 6 

#include <bits/stdc++.h>

using namespace std;

ifstream cin("lantminim.in");
ofstream cout("lantminim.out");

int n , m , x , y , a[101][101] , v[101] , T[101] , p , q , cnt , rez[101];

void bfs(int x)
{
    v[x] = 1;
    T[x] = 0;
    queue <int> Q;
    Q.push(x);
    while(!Q.empty())
    {
        int aux = Q.front();
        Q.pop();
        for(int i = 1 ; i <= n ; i++)
            if(!v[i] && a[aux][i] == 1)
            {
                v[i] = 1;
                Q.push(i);
                T[i] = aux;
            }
    }

}

int main()
{
    cin >> n >> p >> q;

    while(cin >> x >> y)
    {
        a[x][y] = a[y][x] = 1;
    }

    bfs(q);

    int aux = p;
    while(aux != q)
    {
        rez[++cnt] = aux;
        aux = T[aux];
    }
    rez[++cnt] = aux;

    cout << cnt << '\n';
    for(int i = 1 ; i <= cnt; i++)
        cout << rez[i] << " ";
}