Pagini recente » Cod sursa (job #1333746) | Cod sursa (job #2562495) | Cod sursa (job #1845302) | Cod sursa (job #626635) | Cod sursa (job #1760546)
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 45005;
const int kSize = 16;
int n, m, s, t, q, size;
int dfu[kMaxN];
int depth[kMaxN];
int bpath[kSize];
bool insideComp[kMaxN], hasCycle;
vector <int> graph[kMaxN];
vector <int> path;
vector <int> comp;
stack <pair <int, int>> dfsStack;
void noChance() {
printf("No chance!\n");
exit(0);
}
void Back(const int i, const int u, const int f) {
if (i < size && insideComp[f]) {
for (const int v: graph[u]) {
if (insideComp[v]) {
insideComp[v] = false;
bpath[i] = v;
Back(i + 1, v, f);
insideComp[v] = true;
}
}
}
else if (i == size) {
hasCycle = true;
for(int j = 1; j < size; j++) {
path.push_back(bpath[j]);
}
}
}
bool dfsBiconnected(const int u) {
bool ret = false;
dfu[u] = depth[u];
if(u == s || u == t) {
path.push_back(u);
if(u == s) {
swap(s, t);
}
ret = true;
}
for (const int v: graph[u]) {
if (u == q || depth[v] != depth[u] - 1) {
if (!depth[v]) {
depth[v] = depth[u] + 1;
dfsStack.push(make_pair(u, v));
bool goodDirection = dfsBiconnected(v);
ret |= goodDirection;
dfu[u] = min(dfu[u], dfu[v]);
if (depth[u] <= dfu[v]) {
comp.clear();
while (!dfsStack.empty() && dfsStack.top() != make_pair(u, v)) {
comp.push_back(dfsStack.top().second);
dfsStack.pop();
}
comp.push_back(u);
comp.push_back(v);
dfsStack.pop();
size = comp.size();
if (goodDirection) {
for (const int x: comp) {
insideComp[x] = true;
}
if (u == q && !insideComp[s]) {
noChance();
}
const int node = path.back();
insideComp[node] = false;
hasCycle = false;
Back(1, node, u);
if (!hasCycle) {
noChance();
}
for (const int x: comp) {
insideComp[x] = false;
}
}
}
}
else {
dfu[u] = min(dfu[u], depth[v]);
}
}
}
return ret;
}
int main() {
freopen("santa.in", "r", stdin);
freopen("santa.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u].push_back(v);
graph[v].push_back(u);
}
scanf("%d %d %d", &s, &t, &q);
depth[q] = 1;
dfsBiconnected(q);
printf("%u\n", path.size());
for(const int u: path) {
printf("%d ", u);
}
printf("\n");
return 0;
}