Pagini recente » Cod sursa (job #2363573) | Cod sursa (job #1286521) | Cod sursa (job #223024) | Cod sursa (job #2200912) | Cod sursa (job #2379830)
#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<<"No chance";
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);
}
}
}
}