Cod sursa(job #2266994)

Utilizator CronosClausCarare Claudiu CronosClaus Data 23 octombrie 2018 08:38:56
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;

const int mxn = 100 * 1000 + 10;

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

int n, m;

bool viz[ mxn ];
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 ] = lvl[ nod ] + 1;
            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()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1, x, y; i <= m; i++){
        scanf("%d %d", &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 );
    printf("%d\n", s.size());
    for(auto v: s){
        for(auto it: v){
            printf("%d ", it);
        }
        printf("\n");
    }
    return 0;
}