Pagini recente » Cod sursa (job #2083875) | Monitorul de evaluare | Cod sursa (job #3253990) | Cod sursa (job #170674) | Cod sursa (job #3289481)
#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;
}