Cod sursa(job #1908207)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 6 martie 2017 23:35:25
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
#include <algorithm>
#define NMAX 100001

using namespace std;

vector <int> G[NMAX];
vector <int> BC[NMAX];
stack <pair<int,int> > st;
enum colors {white, grey, black};
int prev[NMAX], colors[NMAX];
int d[NMAX], low[NMAX];
int n, nr_c = -1;

void read_graph() {

    int x, y, m;
    ifstream in("biconex.in");
    in >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    in.close();
}

void add_biconex (pair <int, int> pr)
{
    nr_c++;
    int ok = 1;
    while (!st.empty() && st.top() != pr)
    {
        if (ok)
            BC[nr_c].push_back(st.top().second), ok = 0;

        BC[nr_c].push_back(st.top().first);
        st.pop();
    }

    if (!st.empty())
    {
        if (ok)
            BC[nr_c].push_back(st.top().second), ok = 0;

        BC[nr_c].push_back(st.top().first);
        st.pop();
    }
}

void dfs(int node) {

    static int time = 0;
    /** **/
    colors[node] = grey;
    d[node] = ++time;
    low[node] = d[node];
    /** **/
    for (unsigned int i = 0; i < G[node].size(); i++)
    {
        if (colors[G[node][i]] == white) {

            prev[G[node][i]] = node;
            st.push(make_pair(node, G[node][i]));
            dfs(G[node][i]);
            low[node] = min(low[node], low[G[node][i]]);

            if (low[G[node][i]] >= d[node]) {

                add_biconex(make_pair(node, G[node][i]));
            }

        } else if (prev[node] != G[node][i] && colors[G[node][i]] == grey) {

            low[node] = min(low[node], d[G[node][i]]);
        }

    }
    colors[node] = black;
}

void print_biconex() {

    /** print **/
    ofstream out("biconex.out");

    out << nr_c + 1 << "\n";
    for (int i = 0; i <= nr_c; i++)
    {
        for (unsigned int j = 0; j < BC[i].size(); j++)
            out << BC[i][j] << " ";
        out << "\n";
    }
    out.close();
}

int main() {

    read_graph();

    for (int i = 1; i <= n; i++)
        if (colors[i] != black) {

            dfs(i);
            if (!st.empty())
                add_biconex(make_pair(0, 0));
        }

    print_biconex();
    return 0;
}