Cod sursa(job #1165273)

Utilizator cbanu96Banu Cristian cbanu96 Data 2 aprilie 2014 16:33:34
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>


using namespace std;

#define FILEIN "biconex.in"
#define FILEOUT "biconex.out"

#define NMAX 100005
#define MMAX 200005

vector<int> A[NMAX];
int N, M;
int Depth[NMAX], Low[NMAX];

stack<pair<int, int> > St;
vector<vector<int> > Sol;

void AddSol(int fx, int fy) {
    vector<int> Biconex;

    int x, y;
    do {
        x = St.top().first, y = St.top().second, St.pop();
        Biconex.push_back(x);
        Biconex.push_back(y);

    } while ( x != fx && y != fy );

    sort(Biconex.begin(), Biconex.end());
    Biconex.erase(unique(Biconex.begin(), Biconex.end()), Biconex.end());

    Sol.push_back(Biconex);
}

void DF(int nod, int parent, int depth) {
    Depth[nod] = depth;
    Low[nod] = depth;

    for (int i = 0; i < A[nod].size(); i++ ) {
        int y = A[nod][i];

        if ( y == parent ) continue;

        if ( Depth[y] == 0 ) {
            St.push(make_pair(nod, y));
            DF(y, nod, depth+1);
            Low[nod] = min(Low[nod], Low[y]);
            if (Low[y] >= Depth[nod]) {
                // nod = nod articulatie => comp biconexa
                AddSol(nod, y);
            }
        } else {
            Low[nod] = min(Low[nod], Depth[y]);
        }
    }
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d %d", &N, &M);

    for ( int i = 1, x, y; i <= M; i++ ) {
        scanf("%d %d", &x, &y);
        A[x].push_back(y), A[y].push_back(x);
    }

    for ( int i = 1; i <= N; i++ ) {
        if (Depth[i] == 0)
            DF(i, 0, 1);
    }

    printf("%d\n", Sol.size());
    for ( int i = 0; i < Sol.size(); i++ ) {
        for ( int j = 0; j < Sol[i].size(); j++ ) {
            printf("%d ", Sol[i][j]);
        }
        printf("\n");
    }

    return 0;
}