Pagini recente » Cod sursa (job #1887052) | Autori | Cod sursa (job #1372971) | Cod sursa (job #1164282) | Cod sursa (job #1409074)
#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stack>
#define NMAX 45005
#define MMAX 130005
using namespace std;
struct edge {
int a, b;
int which_biconnected;
edge (int _a = 0, int _b = 0, int _which_biconnected = 0): a(_a), b(_b), which_biconnected(_which_biconnected) {}
inline int other (int x) {
return (a + b - x);
}
} edges[MMAX];
inline int common_node (const edge &a, const edge &b) {
if (a.a == b.a || a.a == b.b)
return a.a;
return a.b;
}
int n, m, s, e, q;
vector <int> graph[NMAX];
//Biconnected components
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bitset <NMAX> critical;
vector <vector <int> > biconnecteds;
bitset <NMAX> vis;
int h[NMAX];
int low[NMAX];
stack <int> _stack;
vector <int> aux;
void dfs (int node) {
vis[node] = 1;
int sons_count = 0;
for (vector <int> :: iterator it = graph[node].begin(); it != graph[node].end(); it++)
if (!vis[edges[*it].other(node)]) {
h[edges[*it].other(node)] = low[edges[*it].other(node)] = 1 + h[node];
_stack.push(*it);
dfs(edges[*it].other(node));
if (low[edges[*it].other(node)] >= h[node]) {
critical[node] = true;
while (_stack.top() != *it) {
aux.push_back(_stack.top());
edges[_stack.top()].which_biconnected = biconnecteds.size();
edges[_stack.top()].which_biconnected = biconnecteds.size();
_stack.pop();
}
aux.push_back(_stack.top());
edges[_stack.top()].which_biconnected = biconnecteds.size();
edges[_stack.top()].which_biconnected = biconnecteds.size();
_stack.pop();
biconnecteds.push_back(aux);
aux.clear();
}
if (low[edges[*it].other(node)] < low[node])
low[node] = low[edges[*it].other(node)];
sons_count ++;
}
else {
if (h[edges[*it].other(node)] < h[node] - 1)
_stack.push(*it);
if (h[edges[*it].other(node)] < low[node])
low[node] = h[edges[*it].other(node)];
}
if (!h[node])
critical[node] = (sons_count > 1);
}
inline void test_criticals () {
dfs(1);
for (int i = 1; i <= n; i++) {
cout << i << ' ' << h[i] << ' ' << low[i];
if (critical[i])
cout << " is critical";
cout << endl;
}
}
inline void test_biconnecteds () {
dfs(1);
vector <int> :: iterator it2;
for (vector <vector <int> > :: iterator it = biconnecteds.begin(); it != biconnecteds.end(); it++) {
cout << "Biconnected component " << it - biconnecteds.begin() << " found:" << endl;
for (it2 = it -> begin(); it2 != it -> end(); it2++)
cout << edges[*it2].a << ' ' << edges[*it2].b << endl;
cout << endl;
}
for (int i = 1; i <= m; i++)
cout << edges[i].a << ' ' << edges[i].b << " belongs to biconnected component number " << edges[i].which_biconnected << endl;
cout << endl;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//Finding a road from S to E
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int father[NMAX];
//Uses vis, so vis must be set to 0
void dfs_road (int node) {
vis[node] = true;
for (vector <int> :: iterator it = graph[node].begin(); it != graph[node].end(); it++)
if (!vis[edges[*it].other(node)]) {
father[edges[*it].other(node)] = *it;
dfs_road(edges[*it].other(node));
}
}
//Rebuilds the road from S to E
vector <int> road;
void rebuild_road (int node) {
if (father[node]) {
rebuild_road(edges[father[node]].other(node));
road.push_back(father[node]);
}
}
inline void test_road () {
vis &= 0;
dfs_road(s);
rebuild_road(e);
cout << "The road is:" << endl;
for (vector <int> :: iterator it = road.begin(); it != road.end(); it++)
cout << edges[*it].a << ' ' << edges[*it].b << endl;
cout << endl;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//Gets and solves the Hamiltonian Path queries
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
struct hamiltonian_query {
int s, t;
int which_biconnected;
hamiltonian_query (int _s = 0, int _t = 0, int _which_biconnected = 0): s(_s), t(_t), which_biconnected(_which_biconnected) {}
};
vector <hamiltonian_query> queries;
inline void get_hamiltonian_queries () {
vector <int> :: iterator it;
for (it = graph[q].begin(); it != graph[q].end(); it++)
if (edges[road[0]].which_biconnected == edges[*it].which_biconnected)
break;
if (it == graph[q].end()) {
reverse(road.begin(), road.end());
cout << "s-a dat swap" << endl;
for (it = graph[q].begin(); it != graph[q].end(); it++)
if (edges[road[0]].which_biconnected == edges[*it].which_biconnected)
break;
if (it == graph[q].end())
return ;
}
for (int i = 1; i < road.size(); i++)
if (edges[road[i - 1]].which_biconnected != edges[road[i]].which_biconnected) {
if (!queries.empty())
queries.push_back(hamiltonian_query(queries.back().t, common_node(edges[road[i - 1]], edges[road[i]]), edges[road[i - 1]].which_biconnected));
else
queries.push_back(hamiltonian_query(s, common_node(edges[road[i - 1]], edges[road[i]]), edges[road[i - 1]].which_biconnected));
}
if (!queries.empty())
queries.push_back(hamiltonian_query(queries.back().t, e, edges[road[road.size() - 1]].which_biconnected));
else
queries.push_back(hamiltonian_query(s, e, edges[road[road.size() - 1]].which_biconnected));
}
inline void test_hamiltonian_queries () {
for (int i = 0; i < queries.size(); i++)
cout << "Query " << i << ' ' << queries[i].s << ' ' << queries[i].t << ' ' << queries[i].which_biconnected << endl;
}
//Solves a given query, pushes the solution to vector solution (which will represent the final answer to our problem)
vector <int> solution;
inline void solve_hamiltonian_query (const hamiltonian_query &query) {
}
inline void solve_hamiltonian_queries () {
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline void read_graph () {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> edges[i].a >> edges[i].b;
graph[edges[i].a].push_back(i);
graph[edges[i].b].push_back(i);
}
}
//TO BE FIXED
inline void solve () {
dfs(1);
vis &= 0;
dfs_road(s);
rebuild_road(e);
get_hamiltonian_queries();
}
inline void print_solution () {
if (solution.empty())
cout << "No chance\n";
else {
cout << solution.size() << '\n';
cout << solution.front();
for (int i = 1; i < solution.size(); i++)
cout << ' ' << solution[i];
cout << '\n';
}
}
int main()
{
read_graph();
cin >> s >> e >> q;
//Edge case
if (s == e) {
if (s == q) {
cout << "1\n";
cout << q << '\n';
}
else
cout << "No chance\n";
return 0;
}
solve();
test_biconnecteds();
test_hamiltonian_queries();
//print_solution();
return 0;
}