Cerinţa

Se dă lista muchiilor unui graf neorientat și trei vârfuri p q r . Să se determine un lanț cu extremitățile p q care conține vârful r.

Date de intrare

Fişierul de intrare lant1.in conţine pe prima linie numerele n p q r, reprezentând numărul de vârfuri ale grafului și cele trei 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 lant1.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ț cu extremitățile p q care conține vârful r și are lungimea mai mică decât 2*n este acceptat; lanțul nu trebuie să fie elementar
• pentru toate datele de test există cel puțin un lanț care respectă cerința;

Exemplu

lant1.in

8 5 7 3
1 2
1 3
1 5
2 3
2 5
2 7
3 6
4 6
4 7
5 7
6 8
7 8

lant1.out

5
5 1 3 2 7

#include <bits/stdc++.h>



using namespace std;

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

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

vector <int> G[101];


void bfs(int s)
{
    queue <int>Q;
    Q.push(s);
    v[s] = 1;
    d[s] = 1;
    T[s] = 0;
    while(!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        for(int i : G[x])
            if(!v[i])
            {
                d[i] = d[x] + 1;
                Q.push(i);
                v[i] = 1;
                T[i] = x;
            }

    }
}

int main()
{
    cin >> n >> p >> q >> r;
    while(cin >> x >> y)
    {
        G[x].push_back(y);
        G[y].push_back(x);
    }

    bfs(r);
    int paux = p;
    while (paux != r)
    {
        rez[++cnt] = paux;
        paux = T[paux];
    }
    for (int i = 0; i <= n; ++ i)
        v[i] = 0;
    bfs(q);
    paux = r;
    while (paux != q && paux != 0)
    {
        rez[++cnt] = paux;
        paux = T[paux];
    }
    rez[++cnt] = q;

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