Cod sursa(job #2267008)

Utilizator lulian23Tiganescu Iulian lulian23 Data 23 octombrie 2018 09:26:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>

using namespace std;

const int mxn = 100 * 1000 + 1;

vector< int > g[ mxn ];
vector< vector< int > > s;
stack< int > st;
bool viz[ mxn ];

int n, m;
int low[ mxn ], lvl[ mxn ];


void dfs(int nod){
    viz[ nod ] = 1;
    st.push( nod );

    for(auto it: g[ nod ]){
        if(viz[ it ] == 0){
            lvl[ it ] = low[ it ] = lvl[ nod ] + 1;
            dfs( it );

            if(low[ it ] >= lvl[ nod ]){
                vector< int > v;
                while(st.top() != it){
                    v.push_back( st.top() );
                    st.pop();
                }
                st.pop();
                v.push_back( it );
                v.push_back( nod );
                s.push_back( v );
            }
            low[ nod ] = min(low[ nod ], low[ it ]);
        }
        else{
            low[ nod ] = min(low[ nod ], lvl[ it ]);
        }
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie( 0 );

    ifstream cin("biconex.in");
    ofstream cout("biconex.out");

    cin>> n >> m;
    for(int i = 1, x, y; i <= m; i++){
        cin>> x >> y;
        g[ x ].push_back( y );
        g[ y ].push_back( x );
    }

    for(int i = 1; i <= n; i++)
        if(viz[ i ] == 0)
            dfs( i );
        cout<< s.size() << '\n';

    for(auto v : s){
        for(auto it : v){
            cout<< it << ' ';
        }
        cout<< '\n';
    }
}