Cod sursa(job #2408949)

Utilizator refugiatBoni Daniel Stefan refugiat Data 18 aprilie 2019 15:22:29
Problema Santa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream si("santa.in");
ofstream so("santa.out");
vector<vector<int>> g, comp;
int n, m, start, finish, first;
vector<int> low, h, good;
vector<int> a;
stack<int> st;
bool sol{true};
vector<int> path, cango;

vector<int> newComponent(int node1, int node2) {
    vector<int> comp;
    while(st.top()!=node2) {
        comp.push_back(st.top());
        st.pop();
    }
    comp.push_back(node2);
    comp.push_back(node1);
    st.pop();
    return comp;
}

void Dfs(int node, int f) {
    low[node]=h[node]=h[f]+1;
    st.push(node);
    if(node==finish)
        good[node]=true;

    for(auto next:g[node]) {
        if(next==f)
            continue;

        if(h[next]) {
            low[node]=min(low[node], h[next]);
            continue;
        }

        Dfs(next, node);
        good[node]|=good[next];
        low[node]=min(low[node], low[next]);
        if(h[node]<=low[next]) {
            vector<int> C=newComponent(node, next);
            if(!good[next])
                continue;
            comp.push_back(C);
            a.push_back(node);
        }
    }
}


bool findPath(int node, int target, int r, bool ok) {
    if(ok)
        path.push_back(node);
    cango[node]=false;

    if(r==1&&(node==target||target==0)) {
        return true;
    }
    if(node==target||r==1) {
        cango[node]=true;
        if(ok)
            path.pop_back();
        return false;
    }
    for(auto next:g[node])
        if(cango[next]&&findPath(next, target, r-1, 1)) {
            return true;
        }
    if(ok)
        path.pop_back();
    cango[node]=true;
    return false;
}

int main() {
    si>>n>>m;
    int x, y;
    g=vector<vector<int>>(n+1);
    cango=good=low=h=vector<int>(n+1);
    while(m--) {
        si>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    si>>start>>finish>>first;
    a.push_back(first);
    Dfs(start, 0);
    bool g=false;
    for(auto x: comp[0])
        if(x==first) {
            g=true;
            break;
        }
    if(!g) {
        reverse(comp.begin(), comp.end());
        reverse(a.begin(), a.end());
    }
    g=false;
    for(auto x: comp[0])
        if(x==first) {
            g=true;
            break;
        }
    if(!g)
        sol=false;
    a.front()=first;
    a.back()=0;
    for(auto v:comp)
        for(auto x:v)
            cango[x]=true;
    for(size_t i=0; i<comp.size()&&sol; ++i) {
        cango[a[i]]=true;
        if(!findPath(a[i], a[i + 1], comp[i].size(), 1)) {
            sol=false;
            break;
        }
        if(i+1<comp.size())
            path.pop_back();
        for(auto x:comp[i])
            cango[x]=false;
    }
    if(!sol) {
        so<<"No chance"<<'\n';
    }
    else {
        so<<path.size()<<'\n';
        for(size_t i=0; i<path.size(); ++i) {
            so<<path[i]<<' ';
        }
    }
    return 0;
}