Cod sursa(job #1017142)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 27 octombrie 2013 12:41:11
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

const int NMAX = 100003;

vector <vector <int> > R;
vector <int> G[NMAX];
stack <int> S;
int node_depth[NMAX], min_depth[NMAX], s;

void DFS (const int &node, const int &depth) {

    node_depth[node] = min_depth[node] = depth;
    for (vector <int> :: iterator i = G[node].begin (); i != G[node].end (); ++i)
        if (!node_depth[*i]) {
            S.push (*i);
            DFS (*i, depth + 1);
            min_depth[node] = min (min_depth[node], min_depth[*i]);
            if (node_depth[node] == min_depth[*i]) {
                vector <int> N;
                while (S.top () != *i)
                    N.push_back (S.top ()),
                    S.pop ();
                S.pop ();
                N.push_back (*i);
                N.push_back (node);
                R.push_back (N);
            }
        }
        else
            min_depth[node] = min (min_depth[node], node_depth[*i]);

}

int main () {

    freopen ("biconex.in", "r", stdin);
    freopen ("biconex.out", "w", stdout);
    int N, M, a, b, i;
    scanf ("%d%d", &N, &M);
    for (i = 1; i <= M; ++i)
        scanf ("%d%d", &a, &b),
        G[a].push_back (b),
        G[b].push_back (a);
    for (i = 1; i <= N; ++i)
        if (!node_depth[i])
            DFS (i, 1);
    printf ("%d", R.size ());
    for (vector <vector <int> > :: iterator j = R.begin (); j != R.end (); ++j) {
        printf ("\n");
        for (vector <int> :: iterator k = j->begin (); k != j->end (); ++k)
            printf ("%d ", *k);
    }


}