Pagini recente » Cod sursa (job #2454559) | Cod sursa (job #3279625) | Cod sursa (job #2965757) | Cod sursa (job #2748397) | Cod sursa (job #2515948)
#include <bits/stdc++.h>
#define NMAX 45005
using namespace std;
ifstream f("santa.in");
ofstream g("santa.out");
int n,m,s,e,q,nrSpir,nrq,sol[NMAX];
bitset <NMAX> adj[NMAX];
bitset <NMAX> spir;
bitset <NMAX> viz;
bool findSpiritNodes(int node)
{
viz[node]=true;
if(node==e)
{
spir[node]=true;
nrSpir++;
return true;
}
int i;
bool ok=0;
for(i=1;i<=n;i++)
{
if(adj[node][i] && !viz[i])
{
ok=(ok || findSpiritNodes(i));
}
}
spir[node]=ok;
if(ok)
{
nrSpir++;
return true;
}
return false;
}
bool bkt(int node, int k)
{
sol[k]=node;
viz[node]=true;
if(k==nrSpir) return true;
int i;
bool ok;
for(i=1;i<=n;i++)
{
if(adj[node][i] && !viz[i] && spir[i])
{
ok=bkt(i,k+1);
if(ok) return true;
}
}
sol[k]=0;
viz[node]=false;
return false;
}
int main()
{
int i,j,k;
f>>n>>m;
for(k=1;k<=m;k++)
{
f>>i>>j;
adj[i][j]=adj[j][i]=true;
}
f>>s>>e>>q;
bool ok=findSpiritNodes(s);
for(i=1;i<=n;i++) viz[i]=false;
ok=bkt(q,1);
if(ok)
{
g<<nrSpir<<'\n';
for(i=1;i<=nrSpir;i++)
g<<sol[i]<<' ';
}
else g<<"No chance";
return 0;
}
/*bool normalDF(int node)
{// nu a mai fost utilizat in ultima versiune oups :)))
int i;
viz[node]=true;
nrq++;
st.push(node);
if(nrq==nrSpir) return true;
for(i=1;i<=n;i++)
{
if(adj[node][i] && !viz[i] && spir[i])
{
if(normalDF(i)) return true;
}
}
nrq--;
st.pop();
viz[node]=false;
return false;
}*/