Cod sursa(job #1751269)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 1 septembrie 2016 01:17:19
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 100005;

struct PII {
    int x, y;

    inline PII() { }
    inline PII(int _x, int _y) {
        x = _x;
        y = _y;
    }
};

vector<PII> stk;
int         ant;

vector<int>   g[NMAX],
            bix[NMAX];
bool        art[NMAX],
            gws[NMAX];
int         low[NMAX],
            lvl[NMAX];

void add(int lst) {
    PII top;

    do {
        top = stk.back();
        bix[ant].push_back(top.y);
        stk.pop_back();
    } while(top.x != lst);

    bix[ant].push_back(lst);
    ++ant;
}

void dfs(int u, int p) {
    lvl[u] = lvl[p] + 1;
    low[u] = lvl[p] + 1;
    gws[u] = true;

    for(int v: g[u]) if(v != p) {
        if(gws[v]) {
            low[u] = min(low[u], lvl[v]);
        }
        else {
            stk.push_back( PII(u, v) );
            dfs(v, u);

            low[u] = min(low[u], low[v]);
            if(low[v] >= lvl[u]) {
                art[u] = true;
                add(u);
            }
        }
    }
}

int main(void) {
    freopen("biconex.in",  "r", stdin);
    freopen("biconex.out", "w", stdout);
    int n, m, x, y;

    scanf("%d%d", &n, &m);
    while(m--) {
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i=1; i <= n; ++i)
        if(!gws[i])
            dfs(i, 0);

    printf("%d\n", ant);
    for(int i=0; i<ant; ++i) {
        for(auto j:bix[i])
            printf("%d ", j);
        printf("\n");
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}