Cod sursa(job #3289481)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 27 martie 2025 08:58:24
Problema Santa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9 + 5;

vector<bool> visited;
vector<vector<int> > G;
vector<int> level, low;
stack<int> S;

vector<bool> isCriticalNode;
vector<pair<int, int> > criticalEdges;
vector<vector<int> > biconex;
vector<int> comp;

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void DFS_CB(int v, int t, int root)
{
    visited[v] = true;
    low[v] = level[v] = level[t] + 1;

    S.push(v);

    int nrChildren = 0;

    for(int i = 0; i < G[v].size(); i++)
    {
        int u = G[v][i];
        if(u != t)
        {
            if(visited[u])
            {
                low[v] = min(low[v], level[u]);
                continue;
            }

            DFS_CB(u, v, root);
            low[v] = min(low[v], low[u]);

            nrChildren++;

            if(v != root && level[v] <= low[u])
                isCriticalNode[v] = true;

            if(level[v] < low[u])
                criticalEdges.push_back({v, u});

            if(level[v] <= low[u])
            {
                biconex.push_back(vector<int>(0));

                int x;
                do{
                    x = S.top();
                    S.pop();
                    biconex[biconex.size() - 1].push_back(x);
                    comp[x] = biconex.size() - 1;
                } while(x != u);

                biconex[biconex.size() - 1].push_back(v);
                comp[v] = biconex.size() - 1;
            }
        }
    }

    if(v == root && nrChildren >= 2)
        isCriticalNode[root] = true;
}

void FinishProgram()
{
    cout << "No chance\n";
    exit(0);
}

void Solve()
{
    int N, M, S, E, Q;

    cin >> N >> M;

    G.resize(N + 1);
    visited.resize(N + 1, false);
    isCriticalNode.resize(N + 1, false);
    level.resize(N + 1, INF);
    low.resize(N + 1, INF);
    comp.resize(N + 1, -1);

    for(int i = 1, u , v; i <= M; i++)
    {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    cin >> S >> E >> Q;


    DFS_CB(S, 0, S);

    if(not visited[S]) /// Nu exista un drum de la S la E
        FinishProgram();

    if(find(biconex[comp[S]].begin(), biconex[comp[S]].end(), Q) == biconex[comp[S]].end()) /// S si Q NU sunt in aceeasi comp biconexa
        FinishProgram();
}

int main()
{
    SetInput("santa");

    Solve();

    return 0;
}