Cod sursa(job #1166786)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 3 aprilie 2014 20:21:00
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.68 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

static const int NIL = -1;

vector< vector<int> > G, Components;
int V;
vector<int> Level, MinLevel, CriticalVertices;
vector< pair<int, int> > CriticalEdges;
stack< pair<int, int> > EdgeStack;

template<class Type>
inline void EraseDuplicates(vector<Type> &v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

inline void GetComponent(const pair<int, int> &edge) {
    pair<int, int> topEdge;
    vector<int> component;
    do {
        topEdge = EdgeStack.top();
        EdgeStack.pop();
        component.push_back(topEdge.first);
        component.push_back(topEdge.second);
    } while (topEdge != edge);
    EraseDuplicates<int>(component);
    Components.push_back(component);
}

void DFS(const int x, const int father) {
    MinLevel[x] = Level[x];
    for (vector<int>::const_iterator y = G[x].begin(); y != G[x].end(); ++y) {
        if (Level[*y] != -1)
            continue;
        Level[*y] = Level[x] + 1;
        EdgeStack.push(make_pair(x, *y));
        DFS(*y, x);
        if (MinLevel[*y] > Level[x])
            CriticalEdges.push_back(make_pair(x, *y));
        if (MinLevel[*y] >= Level[x]) {
            CriticalVertices.push_back(x);
            GetComponent(make_pair(x, *y));
        }
    }
    bool usedFather = false;
    for (vector<int>::const_iterator y = G[x].begin(); y != G[x].end(); ++y) {
        if (!usedFather && *y == father)
            usedFather = true;
        else
            MinLevel[x] = min(MinLevel[x], MinLevel[*y]);
    }
}

void Solve() {
    Level = MinLevel = vector<int>(V, -1);
    for (int x = 0; x < V; ++x) {
        if (Level[x] == -1) {
            Level[x] = 0;
            DFS(x, NIL);
        }
    }
    EraseDuplicates<int>(CriticalVertices);
    EraseDuplicates< pair<int, int> >(CriticalEdges);
}

inline void AddEdge(const int x, const int y) {
    G[x].push_back(y);
    G[y].push_back(x);
}

void Read() {
    ifstream cin("biconex.in");
    int E;
    cin >> V >> E;
    G = vector< vector<int> >(V, vector<int>());
    for (; E > 0; --E) {
        int x, y;
        cin >> x >> y;
        AddEdge(x - 1, y - 1);
    }
    cin.close();
}

void Print() {
    ofstream cout("biconex.out");
    cout << int(Components.size()) << "\n";
    for (int i = 0; i < int(Components.size()); ++i) {
        for (vector<int>::const_iterator x = Components[i].begin(); x != Components[i].end(); ++x)
            cout << *x + 1 << " ";
        cout << "\n";
    }
    cout.close();
}

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