Cod sursa(job #1502734)

Utilizator stefanzzzStefan Popa stefanzzz Data 14 octombrie 2015 23:19:18
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <stdio.h>
#include <vector>
#define MAXN 100005
#define MIN(a, b) (((a) < (b))?(a):(b))
using namespace std;

int n, m, x, y, lvl[MAXN], low[MAXN], nrBcc;
vector<int> G[MAXN], bcc[MAXN];
vector< pair<int, int> > st;

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

    bool visp = 0;
    for(auto x: G[u]) {
        if(!lvl[x]) {
            st.push_back(make_pair(u, x));
            DFS(x, u);
            low[u] = MIN(low[u], low[x]);

            if(low[x] >= lvl[u]) {
                ++nrBcc;
                pair<int, int> e;
                do {
                    e = st.back();
                    st.pop_back();
                    bcc[nrBcc].push_back(e.second);
                } while(e.first != u);
                bcc[nrBcc].push_back(u);
            }
        }
        else {
            if(x != p || visp) low[u] = MIN(low[u], lvl[x]);
            if(x == p) visp = 1;
        }
    }
}

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

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

    DFS(1, 0);
    printf("%d\n", nrBcc);
    for(int i = 1; i <= nrBcc; i++, printf("\n"))
        for(auto x: bcc[i])
            printf("%d ", x);

    return 0;
}