Cod sursa(job #1689825)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 14 aprilie 2016 16:39:22
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int NMAX = 100005;

vector <int> graph[NMAX];

vector <vector <int> > sol;
stack <pair <int, int> > _stack;

void extract(pair <int, int> edge) {
    vector <int> aux;
    while (_stack.top() != edge) {
        aux.push_back(_stack.top().second);
        _stack.pop();
    }

    aux.push_back(_stack.top().first);
    aux.push_back(_stack.top().second);
    _stack.pop();

    sol.push_back(aux);
}

int h[NMAX];
int low[NMAX];

bool vis[NMAX];
void dfs(int node) {
    vis[node] = true;
    low[node] = h[node];

    for (auto it: graph[node]) {
        if (!vis[it]) {
            h[it] = 1 + h[node];

            _stack.push(make_pair(node, it));
            dfs(it);

            if (low[it] < low[node])
                low[node] = low[it];
            else if (low[it] >= h[node])
                extract(make_pair(node, it));
        }
        else if (h[it] < low[node])
            low[node] = h[it];
    }
}

int main()
{
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");

    int n = 0, m = 0;
    cin >> n >> m;

    int a, b;
    while (m --) {
        cin >> a >> b;

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    h[1] = 1;
    dfs(1);

    cout << sol.size() << '\n';
    for (auto it: sol)
        for (int i = 0; i < it.size(); ++ i)
            cout << it[i] << " \n"[i + 1 == it.size()];

    cin.close();
    cout.close();
    return 0;
}