Cod sursa(job #1330535)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 30 ianuarie 2015 19:22:21
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <vector>
#include <stack>

#define Nmax 100100
#define neighbour Graph[node][i]

using namespace std;

vector <int> Graph[Nmax], Component[Nmax];
stack < pair<int, int> > Stack;
int N, nrC, Level[Nmax], High[Nmax];

inline void addEdge(int a, int b) {
    Stack.push(make_pair(a, b));
}
void saveComponent(int a, int b) {

    int x, y;

    nrC++;
    do {
        x = Stack.top().first;
        y = Stack.top().second;
        Component[nrC].push_back(y);
        Stack.pop();
    } while(x != a && y != b);

    Component[nrC].push_back(x);
}
void BellmanFord(int node, int father) {

    Level[node] = Level[father] + 1;
    High[node] = Level[node];

    for(int i = 0; i < Graph[node].size(); i++)
        if(neighbour != father) {

            if(Level[neighbour] == 0) {
                addEdge(node, neighbour);
                BellmanFord(neighbour, node);
                if(High[neighbour] >= Level[node])
                    saveComponent(node, neighbour);
            }

            if(High[neighbour] < High[node])
                High[node] = High[neighbour];
        }
}
void Read() {

    int x, y, M;
    ifstream in("biconex.in");
    in >> N >> M;

    while(M--) {
        in >> x >> y;
        Graph[x].push_back(y);
        Graph[y].push_back(x);
    }

    in.close();
}
void Write() {

    int i, j;
    ofstream out("biconex.out");

    out << nrC << '\n';
    for(i = 1; i <= nrC; i++) {
        for(j = 0; j < Component[i].size(); j++)
            out << Component[i][j] << ' ';
        out << '\n';
    }

    out.close();
}
int main() {

    Read();
    BellmanFord(1, 0);
    Write();

    return 0;
}