Cod sursa(job #957885)

Utilizator SmarandaMaria Pandele Smaranda Data 6 iunie 2013 12:14:54
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
#include <cstdio>
#include <vector>

using namespace std;

struct Edge{
    long value, ind;
};

const long N = 100001, M = 200001, INF = 2e9;
long n, m, level [N], dp [N], lvl = -1, dad [N], bad [M], ord, num = 0;
bool used [N], used1 [N];
Edge temp;
vector <Edge> graph [N];
vector <long> sol [N];

void read (){
    long i, x, y;
    Edge temp;
    scanf ("%ld%ld", &n, &m);
    for (i = 1; i <= m; i ++){
        scanf ("%ld%ld", &x, &y);
        temp.value = y;
        temp.ind = i;
        graph [x].push_back (temp);
        temp.value = x;
        graph [y].push_back (temp);
    }
}

void dfs (long x, long ind){
    long i;
    Edge temp;
    used [x] = true;
    level [x] = ++ lvl;
    dp [x] = INF;
    for (i = 0; i < graph [x].size (); ++ i){
        temp = graph [x][i];
        if (!used [temp.value]){
            dad [temp.value] = x;
            dfs (temp.value, temp.ind);
            dp [x] = min (dp [x], dp [temp.value]);
        }
        else
            if (dad [x] != temp.value)
                dp [x] = min (dp [x], level [temp.value]);
    }
    if (dp [x] >= level [x]){
        bad [ind] = 1;
        if (dad [x] != 0){
            sol [++ ord].push_back (dad [x]);
            sol [ord].push_back (x);
        }
    } // critica dad [x], x
    lvl --;
}

void componente_conexe (long x){
    long i;
    Edge temp;
    used1 [x] = 1;
    sol [ord].push_back (x);
    for (i = 0; i < graph [x].size (); i ++){
        temp = graph [x][i];
        if (!used1 [temp.value] && !bad [temp.ind])
            componente_conexe (temp.value);
    }
}

void solve (){
    long i, g, j;
    ord = 0;
    for (i = 1; i <= n; i ++)
        if (!used [i]){
            dfs (i, 0);
        }
    for (i = 1; i <= n; i ++)
        if (!used1 [i]){
            ord ++;
            componente_conexe (i);
            if (sol [ord].size () == 1) {
                sol [ord].clear ();
                ord --;
            }
        }


    printf ("%ld\n", ord);
    for (i = 1; i <= ord; i ++){
        for (j = 0; j < sol [i].size (); j ++)
            printf ("%ld ",sol [i][j]);
        printf ("\n");
    }
}

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

    read ();
    solve ();
    return 0;
}