Cod sursa(job #1760546)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 20 septembrie 2016 22:19:51
Problema Santa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#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;
}