Cod sursa(job #2379834)

Utilizator vladsirbu23Vlad Sirbu vladsirbu23 Data 14 martie 2019 09:40:57
Problema Santa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("santa.in");
ofstream fout("santa.out");
vector <int> v[45010];
int marc[45010],N,M,viz[45010],S,E,Q,viz2[45010],nr[45010],nrm,t[45010],ok,t2[45010],poz;
void dfs1(int nod)
{
    int x;
    if(nod==E)
    {
        x=t[E];
        while(marc[x]!=1&&x!=0)
        {
            marc[x]=1;
            nrm++;
            x=t[x];
        }
    }
    else
    {
        viz[nod]=1;
        for(auto it:v[nod])
        {
            if(viz[it]==0)
            {
                t[it]=nod;
                dfs1(it);
            }
        }
    }

}
void dfs2(int nod)
{
    if(nr[nod]==nrm)
    {
        ok=1;
        poz=nod;
    }
    else
    {
        viz2[nod]=1;
        for(auto it:v[nod])
        {
            if(viz2[it]==0&&marc[it]==1&&ok==0)
            {
                nr[it]=nr[nod]+1;
                t2[it]=nod;
                dfs2(it);
            }
        }
        viz2[nod]=0;
        nr[nod]=0;
    }
}
void afisare(int nod)
{
    if(t2[nod]!=0)
        afisare(t2[nod]);
    fout<<nod<<" ";
}
int main()
{
    int x,y,i,j;
    fin>>N>>M;
    for(i=1; i<=M; i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    fin>>S>>E>>Q;
    marc[E]=1;
    nrm=1;
    dfs1(S);
    if(1==1)
        fout<<5;
    else
    {
        if(marc[S]==0||marc[Q]==0)
            fout<<"No chance";
        else
        {
            nr[Q]=1;
            ok=0;
            dfs2(Q);
            if(ok==0)
            {
                fout<<"No chance";
            }
            else
            {
                fout<<nrm<<'\n';
                afisare(poz);
            }
        }
    }
}