Cod sursa(job #2127943)

Utilizator Andrei2000Andrei Mihailescu Andrei2000 Data 11 februarie 2018 11:46:07
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("biconex.in");
ofstream fout ("biconex.out");

const int nmax=100002;

stack <int> stk;
vector <int> G[nmax];

int n,m,v[nmax],l[nmax];

vector< vector<int> > E;
void bc(int qq, int q){
    vector <int> x;
    int tx;
    x.push_back(qq);
    do{
        x.push_back(tx=stk.top());
        stk.pop();
    }
    while(tx!=q);
    E.push_back(x);
}

void dfs(int no, int fn, int lev){
    v[no]=l[no]=lev;
    stk.push(no);
    for(auto q: G[no]){
        if(q==fn)continue;
        if(!v[q]){
            dfs(q,no,lev+1);
            l[no]=min(l[no],l[q]);
            if(l[q]>=v[no])bc(no,q);
        }
        else l[no]=min(l[no],v[q]);
    }
}

int main()
{
    int a,b;
    fin>>n>>m;
    for(int i=1;i<=m;++i){
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,0,1);
    fout<<E.size()<<'\n';
    for (int i=0;i<E.size();++i){
        for(int j=0;j<E[i].size();++j)
            fout<<E[i][j]<<' ';
        fout<<'\n';
    }
    return 0;
}