Cod sursa(job #838275)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 19 decembrie 2012 11:10:39
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
#include <cstdio>
#include <cassert>

#include <algorithm>
#include <vector>
#include <stack>
#include <map>

#define x first
#define y second

using namespace std;

typedef vector<int>::iterator vii;

const int MaxN = 100005;
const int MaxE = 200005;

map<pair<int, int>, int> EIndex;
vector<int> G[MaxN];
int N, Level[MaxN], MinLevel[MaxN];
bool CriticalV[MaxN], CriticalE[MaxE];
stack< pair<int, int> > Stack;
vector< vector<int> > BC;

inline void DetermineBC(int X, int Y) {
    vector<int> Component;
    int NewX, NewY;
    do {
        NewX = Stack.top().x, NewY = Stack.top().y;
        Stack.pop();
        Component.push_back(NewX), Component.push_back(NewY);
    } while (NewX != X || NewY != Y);
    sort(Component.begin(), Component.end());
    Component.erase(unique(Component.begin(), Component.end()), Component.end());
    BC.push_back(Component);
}

void DFS(int X, int F) {
    MinLevel[X] = Level[X];
    int NSons = 0;
    for (vii Y = G[X].begin(); Y != G[X].end(); ++Y) {
        if (Level[*Y] == 0) {
            ++NSons;
            Stack.push(make_pair(X, *Y));
            Level[*Y] = Level[X] + 1;
            DFS (*Y, X);
            if (MinLevel[*Y] > Level[X])
                CriticalE[EIndex[make_pair(X, *Y)]] = true;
            if (MinLevel[*Y] >= Level[X])
                DetermineBC(X, *Y), CriticalV[X] = true;
        }
    }
    bool UsedF = false;
    for (vii Y = G[X].begin(); Y != G[X].end(); ++Y) {
        if (*Y == F && !UsedF)
            UsedF = true;
        else
            MinLevel[X] = min(MinLevel[X], MinLevel[*Y]);
    }
    if (X == F)
        CriticalV[X] = NSons > 1;
}

void Solve() {
    for (int X = 1; X <= N; ++X) {
        if (Level[X] == 0) {
            Level[X] = 1; DFS(X, X);
        }
    }
}

void Read() {
    assert(freopen("biconex.in", "r", stdin));
    int M; assert(scanf("%d %d", &N, &M) == 2);
    for (int i = 0; i < M; ++i) {
        int X, Y; assert(scanf("%d %d", &X, &Y));
        EIndex[make_pair(X, Y)] = EIndex[make_pair(Y, X)] = i;
        G[X].push_back(Y), G[Y].push_back(X);
    }
}

void Print() {
    assert(freopen("biconex.out", "w", stdout));
    printf("%d\n", static_cast<int>(BC.size()));
    for (size_t i = 0; i < BC.size(); ++i, printf("\n"))
        for (vii X = BC[i].begin(); X != BC[i].end(); ++X)
            printf("%d ", *X);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}