Cod sursa(job #2223560)

Utilizator berindeiChesa Matei berindei Data 20 iulie 2018 17:41:43
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;
int const NMAX=1e5+100;
ifstream in("biconex.in");
ofstream out("biconex.out");

vector<int> g[NMAX];
stack<int> stiva;
vector< vector<int> > ans;
bitset<NMAX> viz;
int low[NMAX], h[NMAX];

void addsol(int n){
    vector<int> sol;
    while(stiva.top()!=n){
        sol.push_back(stiva.top());
        stiva.pop();
    }
    sol.push_back(n);
    ans.push_back(sol);
}

void dfs(int n, int tata, int &rad){
    stiva.push(n);
    viz[n]=true;
    h[n]=h[tata]+1;
    low[n]=h[n];
    for (auto fiu: g[n]){
        if (fiu==tata) continue;
        if (viz[fiu])
            low[n]=min(low[n], h[fiu]);
        else{
            dfs(fiu, n, rad);
            if (low[fiu]>=h[n])
                addsol(n);
            else
                low[n]=min(low[fiu], low[n]);
        }
    }
}

int main(){
    int n, m, n1, n2;
    in >> n >> m;
    for (int i=1; i<=m; i++){
        in >> n1 >> n2;
        g[n1].push_back(n2);
        g[n2].push_back(n1);
    }
    for (int i=1; i<=n; i++)
        if (!viz[i]) dfs(i, 0, i);
    out << ans.size() << '\n';
    for (auto& x: ans){
        for (auto y: x)
            out << y << ' ';
        out << '\n';
    }
}