Cod sursa(job #1811635)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 21 noiembrie 2016 14:07:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 10;

bool used[nmax];

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

vector < pair < int, int > > s;

void input() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);

        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void get_biconex(pair < int, int > edge) {
    ++cnt;
    while (true) {
        pair < int, int > act = s.back();
        s.pop_back();

        ans[cnt].push_back(act.second);
        if (act == edge) break;
    }
    ans[cnt].push_back(edge.first);
}

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;
        }

        s.push_back({node, it});
        lvl[it] = lvl[node] + 1; dfs(it);

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

void output() {
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; ++i, printf("\n"))
        for (auto &it : ans[i])
            printf("%d ", it);
}

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

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

    return 0;
}