Cod sursa(job #984747)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 15 august 2013 12:19:00
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAX_N = 100002;

typedef struct Edge {
    int x, y;
};

int N, M;
int Level[MAX_N], MinLevel[MAX_N], Father[MAX_N];
vector < int > v[MAX_N];
vector < vector < int > > BC;
stack < Edge > st;

inline bool Edge_cmp(Edge a, Edge b) {
    if(a.x != b.x || a.y != b.y)
        return 1;
    return 0;
}

inline void DFS(int x) {
    MinLevel[x] = Level[x];
    for(size_t i = 0; i < v[x].size(); ++i) {
        int y = v[x][i];
        if(Father[y])
            continue;
        Father[y] = x, Level[y] = Level[x] + 1;
        Edge A;
        A.x = x, A.y = y;
        st.push(A);
        DFS(y);
        if(MinLevel[y] >= Level[x]) {
            vector < int > a;
            while(Edge_cmp(st.top(), A) == true)
                a.push_back(st.top().x), a.push_back(st.top().y), st.pop();
            a.push_back(st.top().x), a.push_back(st.top().y), st.pop();
            BC.push_back(a);
        }
    }

    for(size_t i = 0; i < v[x].size(); ++i)
        if(v[x][i] != Father[x])
            MinLevel[x] = min(MinLevel[x], MinLevel[v[x][i]]);
}

int main() {
    ifstream f("biconex.in");
    ofstream g("biconex.out");

    f >> N >> M;
    for(int i = 1, x, y; i <= M; ++i) {
        f >> x >> y;
        v[x].push_back(y), v[y].push_back(x);
    }

    for(int i = 1; i <= N; ++i)
        if(!Father[i]) {
            Father[i] = i;
            DFS(i);
        }

    g << BC.size() << "\n";
    for(size_t i = 0; i < BC.size(); ++i) {
        sort(BC[i].begin(), BC[i].end());
        for(size_t j = 0; j < BC[i].size(); ++j)
            if(j == 0 || BC[i][j] != BC[i][j-1])
                g << BC[i][j] << " ";
        g << "\n";
    }

    f.close();
    g.close();

    return 0;
}