Cod sursa(job #606516)

Utilizator SpiderManSimoiu Robert SpiderMan Data 4 august 2011 17:16:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
# include <algorithm>
# include <cstdio>
# include <cstring>
# include <stack>
# include <vector>
using namespace std;

# define x first
# define y second

const char *FIN = "biconex.in", *FOU = "biconex.out";
const int MAX = 100005;

vector <int> G[MAX];
vector < vector <int> > C;
stack < pair <int, int> > stiva;
int N, M, df[MAX], back[MAX];

inline void getmin (int &a, int b) {
    a = a < b ? a : b ;
}

inline void ck (vector <bool> &viz, vector <int> &aux, int val) {
    if (viz[val]) return ;
    aux.push_back (val), viz[val] = 1;
}

inline void extrage (int x, int y) {
    vector <int> aux; vector <bool> viz;
    viz.resize (N + 1, 0);
    for (pair <int, int> ex (-1, -1); ex.x != x || ex.y != y; ck (viz, aux, ex.x), ck (viz, aux, ex.y))
        ex = stiva.top (), stiva.pop ();
    C.push_back (aux);
}

void dfs (int N, int F, int cnt) {
    df[N] = back[N] = cnt;
    for (vector <int> :: iterator it = G[N].begin (); it != G[N].end (); ++it) {
        if (*it != F) {
            if (df[*it] == -1) {
                stiva.push (make_pair (N, *it));
                dfs (*it, N, cnt + 1);
                getmin (back[N], back[*it]);
                if (back[*it] >= df[N]) extrage (N, *it);
            } else getmin (back[N], df[*it]);
        }
    }
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    scanf ("%d %d", &N, &M);
    for (int i = 1, x, y; i <= M; ++i) {
        scanf ("%d %d", &x, &y);
        G[x].push_back (y);
        G[y].push_back (x);
    }
    memset (df, -1, sizeof (df));
    dfs (1, 0, 0);
    printf ("%u\n", C.size ());
    for (size_t i = 0; i < C.size (); ++i, printf ("\n"))
        for (size_t j = 0; j < C[i].size (); ++j)
            printf ("%d ", C[i][j]);
}