Cod sursa(job #2488268)

Utilizator mirceaisherebina mircea mirceaishere Data 6 noiembrie 2019 17:17:48
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout ("biconex.out");

int n, m, t, i, j, x, y, v[200010], niv[200010], low[200010], componente, f[200010], sol;
vector<int>cmp[200010];
vector<int>a[200010];
stack<int>stiva;

void dfs(int nod, int k, int tata){
    v[nod]=1;
    niv[nod]=k;
    low[nod]=k;
    stiva.push(nod);
    for(int i=0; i<a[nod].size(); i++){
        int vecin=a[nod][i];
        if(vecin!=tata){
            if(v[vecin]==1){
                low[nod]=min(low[nod], niv[vecin]);
            }else{
                dfs(vecin, k+1, nod);
                low[nod]=min(low[nod], low[vecin]);
                if(low[vecin]>=niv[nod]){
                    componente++;
                    f[nod]++;
                    int aux;
                    do{
                        aux = stiva.top();
                        cmp[componente].push_back(stiva.top());
                        stiva.pop();
                    }while(aux!=vecin);

                    cmp[componente].push_back(nod);
                }
            }
        }
    }

}

int main(){
    fin>>n>>m;
    for(i=1; i<=m; i++){
        fin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1, 1, 0);
    fout<<componente<<"\n";
    for(i=1; i<=componente; i++){
        for(j=0; j<cmp[i].size(); j++){
            fout<<cmp[i][j]<<" ";
        }
        fout<<"\n";
    }
}