Pagini recente » Cod sursa (job #2206846) | Cod sursa (job #2883140) | Cod sursa (job #1109928) | Cod sursa (job #3149180) | Cod sursa (job #3243408)
#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;
}