Cod sursa(job #2419650)

Utilizator Alex18maiAlex Enache Alex18mai Data 9 mai 2019 09:21:27
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
//ALEX ENACHE

#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>

using namespace std;

//#include <iostream>
#include <fstream>
ifstream cin ("biconex.in");ofstream cout ("biconex.out");

vector < int > gr[100100];

int lv[100100];
int MIN[100100];
int cont;
vector < int > ans[100100];
stack < int > s;

void dfs (int nod , int dad){
    lv[nod] = lv[dad]+1;
    MIN[nod] = lv[nod];
    s.push(nod);
    for (auto &x : gr[nod]){
        if (lv[x]){
            if (x != dad){
                MIN[nod] = min(MIN[nod] , lv[x]);
            }
        }
        else{
            dfs(x , nod);
            MIN[nod] = min(MIN[nod] , MIN[x]);
            if (MIN[x] >= lv[nod]){
                cont++;
                while (s.top() != x){
                    ans[cont].push_back(s.top());
                    s.pop();
                }
                ans[cont].push_back(x);
                ans[cont].push_back(nod);
                s.pop();
            }
        }
    }
}

int main() {

    //freopen("input", "r", stdin);freopen("output", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << setprecision(10) << fixed;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    srand(time(nullptr));


    int n , m;
    cin>>n>>m;

    for (int i=1; i<=m; i++){
        int a , b;
        cin>>a>>b;
        gr[a].push_back(b);
        gr[b].push_back(a);
    }

    for (int i=1; i<=n; i++){
        if (!lv[i]){
            dfs(i , 0);
        }
    }

    cout<<cont<<'\n';
    for (int i=1; i<=cont; i++){
        for (auto &x : ans[i]){
            cout<<x<<" ";
        }
        cout<<'\n';
    }

    return 0;
}