Cod sursa(job #1409074)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 30 martie 2015 13:16:38
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 8.6 kb
#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;
}