Cod sursa(job #2113503)

Utilizator cristina_borzaCristina Borza cristina_borza Data 24 ianuarie 2018 17:47:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <bits/stdc++.h>

#define se second
#define fi first

using namespace std;

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

const int Dim = 1e5 + 5;

int niv[ Dim ], mn[ Dim ];
int n, m, sz, x, y;

bool use[ Dim ];

vector <int> G[ Dim ], sol[ Dim ];
stack <pair <int, int> > stk;

void add_sol ( int node1, int node2 ) {
    ++sz;
    while ( stk.size() != 0 && (stk.top().fi != node1 || stk.top().se != node2)) {
        sol[ sz ].push_back ( stk.top().fi );
        sol[ sz ].push_back ( stk.top().se );

        stk.pop();
    }

    if ( stk.size() ) {
        sol[ sz ].push_back ( stk.top().fi );
        sol[ sz ].push_back ( stk.top().se );

        stk.pop();
    }
}

void dfs (int node, int tata, int nivel) {
    niv[ node ] = mn[ node ] = nivel;
    use[ node ] = 1;

    for (vector <int> :: iterator it = G[ node ].begin(); it != G[ node ].end(); ++ it) {
        if (use[ *it ] == 0) {
            stk.push ({node, *it});

            dfs ( *it, node, nivel + 1);
            mn[ node ] = min ( mn[ node ], mn[ *it ]);

            if ( mn[ *it ] >= niv[ node ]) {
                add_sol (node, *it);
            }
        }

        else {
            mn[ node ] = min ( mn[ node ], niv[ *it ]);
        }
    }
}

void afis ( ) {
    g << sz << '\n';
    for (int i = 1; i <= sz; ++ i) {
        sort (sol[ i ].begin(), sol[ i ].end());
        int lst = 0;

        for (vector <int> :: iterator it = sol[ i ].begin(); it != sol[ i ].end(); ++ it) {
            if ( *it != lst) {
                g << *it << " ";
                lst = *it;
            }
        }

        g << '\n';
    }
}

int main() {
    f >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        f >> x >> y;

        G[ x ].push_back ( y );
        G[ y ].push_back ( x );
    }

    dfs (1, 0, 0);
    afis ( );

    return 0;
}