Cod sursa(job #1765683)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 26 septembrie 2016 21:56:41
Problema Componente biconexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include<fstream>
#include<vector>
#include<stack>

using namespace std;

ifstream fin ("biconex.in"); ofstream fout ("biconex.out");

typedef vector< int > graf;

const int nmax = 1e5;
const int inf = (1 << 30) - 1 + (1 << 30);
int h[nmax + 1], d[nmax + 1];
graf g[nmax + 1];

stack< pair<int, int> > st;
vector< vector< int > > sol;

inline int min2 (int a, int b) {
    return (a < b ? a : b);
}
void scoate (pair<int, int> c) {
    vector< int > aux;
    while (!st.empty() && st.top() != c) {
        aux.push_back(st.top().second);
        st.pop();
    }
    aux.push_back( c.second );
    aux.push_back( c.first );
    st.pop();

    sol.push_back( aux );
}
void dfs (int nod, int tata) {
    for (auto it : g[ nod ]) {
        if (it != tata) {
            if (h[ it ] == inf) {
                h[ it ] = h[ nod ] + 1;
                st.push( make_pair(nod, it) );
                dfs(it, nod);

                d[ nod ] = min2(d[ nod ], d[ it ]);
                if (d[ it ] >= h[ nod ]) {
                    scoate( make_pair(nod, it) );
                }
            } else {
                d[ nod ] = min2(d[ nod ], h[ it ]);
            }
        }
    }
}
int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        int x, y;
        fin >> x >> y;
        g[ x ].push_back( y );
        g[ y ].push_back( x );
    }

    for (int i = 1; i <= n; ++ i) {
        h[ i ] = inf;
    }
    h[ 0 ] = 0;
    dfs(1, 0);

    fout << (int)sol.size() << "\n";
    for (auto it : sol) {
        for (auto it2 : it) {
            fout << it2 << " ";
        }
        fout << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}