Cod sursa(job #3243408)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 18 septembrie 2024 14:08:11
Problema Santa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

ifstream f("santa.in");
ofstream g("santa.out");

int n, m, s, e, q, fr[45005], tata[45005], ok = -1, nr;
int nivel[45005], nma[45005], c, frv[45005];
vector<int> a[45005], bic[45005];
stack<int> St;

void biconex(int k, int dad)
{
    St.push(k); fr[k] = 1;
    nma[k] = nivel[k] = nivel[dad] + 1;
    for(auto x : a[k])
        if(x != dad)
        {
            if(fr[x])
                nma[k] = min(nma[k], nivel[x]);
            else
            {
                biconex(x, k);
                nma[k] = min(nma[k], nma[x]);

                if(nivel[k] <= nma[x])
                {
                    c ++;
                    while(St.top() != x)
                        bic[c].push_back(St.top()), St.pop();

                    St.pop();
                    bic[c].push_back(x);
                    bic[c].push_back(k);
                }
            }
        }
}

void bfs(int nod)
{
    queue<int> Q;
    while(!Q.empty()) Q.pop();

    Q.push(nod); fr[nod] = 1;
    while(!Q.empty())
    {
        int k = Q.front();
        Q.pop();
        if(frv[k]){
            ok = k;
            break;
        }

        for(auto x : a[k])
            if(!fr[x])
            {
                fr[x] = fr[k] + 1; tata[x] = k;
                Q.push(x);
            }
    }
}

void afis(int nod)
{
    if(nod == 0)
        return;

    afis(tata[nod]);
    g << nod << " ";
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int x, y; f >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    f >> s >> e >> q;

    biconex(s, 0);

    if(!fr[e]){
        g << "No chance";
        return 0;
    }

    int p = 0;
    for(int i = 1; i <= c && !p; i ++)
        for(int j = 0; j < bic[i].size(); j ++)
            if(bic[i][j] == s)
                p = i;

    for(int i = 1; i <= n; i ++)
        fr[i] = 0;

    for(int i = 0; i < bic[p].size(); i ++)
        frv[bic[p][i]] ++;

    bfs(q);
    if(ok == -1){
        g << "No chance";
        return 0;
    }

    g << fr[ok] + bic[p].size() - 1 << '\n';
    afis(ok);
    int ind = 0;
    for(int i = 0; i < bic[p].size() && !ind; i ++)
        if(bic[p][i] == ok)
            ind = i;

    ind ++;
    for(int i = ind; i < bic[p].size(); i ++)
        g << bic[p][i] << " ";

    for(int i = 0; i < ind - 1; i ++)
        g << bic[p][i] << " ";
    return 0;
}