Cod sursa(job #1105619)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 11 februarie 2014 21:59:28
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.69 kb
#include <cstdio>
#include <cstring>
#include <cassert>

#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <map>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef vector<int>::iterator it;
typedef pair<int, int> Edge;

const int oo = 0x3f3f3f3f;
const int MAX_N = 100099;
const int NIL = -1;

vector<int> G[MAX_N];
int N, Father[MAX_N], Level[MAX_N], MinLevel[MAX_N];
stack<Edge> Stack;
vector< vector<int> > BC;
vector<Edge> CriticalEdges;
vector<int> CriticalVertices;

template<class T>
inline void EliminateDuplicates(vector<T> &V) {
    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());
}

inline void DetermineBC(Edge E) {
    vector<int> Component;
    Edge CurrentE;
    do {
        CurrentE = Stack.top(); Stack.pop();
        Component.push_back(CurrentE.x); Component.push_back(CurrentE.y);
    } while (CurrentE != E);
    EliminateDuplicates<int>(Component);
    BC.push_back(Component);
}

void DFS(int X) {
    MinLevel[X] = Level[X];
    for (it Y = G[X].begin(); Y != G[X].end(); ++Y) {
        if (Father[*Y] != NIL)
            continue;
        Father[*Y] = X; Level[*Y] = Level[X] + 1;
        Stack.push(Edge(X, *Y));
        DFS(*Y);
        if (MinLevel[*Y] > Level[X])
            CriticalEdges.push_back(Edge(X, *Y));
        if (MinLevel[*Y] >= Level[X]) {
            DetermineBC(Edge(X, *Y));
            CriticalVertices.push_back(X);
        }
    }
    bool UsedFather = false;
    for (it Y = G[X].begin(); Y != G[X].end(); ++Y) {
        if (*Y == Father[X] && !UsedFather)
            UsedFather = true;
        else
            MinLevel[X] = min(MinLevel[X], MinLevel[*Y]);
    }
}

void Solve() {
    memset(Father, NIL, sizeof(Father));
    for (int X = 1; X <= N; ++X) {
        if (Father[X] == NIL) {
            Father[X] = X; Level[X] = 0;
            DFS(X);
        }
    }
    EliminateDuplicates<int>(CriticalVertices);
    EliminateDuplicates<Edge>(CriticalEdges);
}

void Read() {
    assert(freopen("biconex.in", "r", stdin));
    int M; assert(scanf("%d %d", &N, &M) == 2);
    for (; M > 0; --M) {
        int X, Y; assert(scanf("%d %d", &X, &Y) == 2);
        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) {
        for (it X = BC[i].begin(); X != BC[i].end(); ++X)
            printf("%d ", *X);
        printf("\n");
    }
}

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