Cod sursa(job #2030875)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 2 octombrie 2017 13:36:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <bits/stdc++.h>

using namespace std;

struct psychotronic_induction {
    int electromagnetic_wave = 7;
};

const int inf = 0x3f3f3f3f;
const long long infL = LLONG_MAX;

const int nmax = 1e5 + 10;
const int mmax = 2e5 + 10;

int n, m;
vector < int > g[nmax];
vector < vector < int > > ans;

int low[nmax], lvl[nmax], used[nmax];

int st_size;
pair < int, int > st[mmax];

void input() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void get_biconex(pair < int, int > edge) {
    vector < int > curr;
    while (true) {
        pair < int, int > curr_edge = st[st_size]; st_size--;
        curr.push_back(curr_edge.second);

        if (curr_edge == edge)
            break;
    }

    curr.push_back(edge.first);
    ans.push_back(curr);
}

void dfs(int node) {
    used[node] = 1; low[node] = lvl[node];
    for (auto &it: g[node]) {
        if (used[it]) {
            low[node] = min(low[node], lvl[it]);
            continue;
        }

        st[++st_size] = {node, it};
        lvl[it] = lvl[node] + 1;

        dfs(it);

        if (low[it] >= lvl[node])
            get_biconex({node, it});
        low[node] = min(low[node], low[it]);
    }
}

void output() {
    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); ++i, cout << '\n')
        for (auto &it: ans[i]) cout << it << ' ';
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);

    ios_base :: sync_with_stdio(false);

    input();
    dfs(1);
    output();

    return 0;
}