Cod sursa(job #2490704)

Utilizator MihneaGhiraMihnea MihneaGhira Data 10 noiembrie 2019 18:40:14
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,k,componente,m,x,y;
int NIV[100001],low[100001],v[100001],F[100001];
stack<int> stiva;
vector<int> L[100001],C[100001];

void dfs(int nod, int niv, int tata){
    v[nod]=1;
    low[nod]=niv;
    NIV[nod]=niv;
    stiva.push(nod);
    for(int i=0;i<L[nod].size();i++){
        int vecin=L[nod][i];
        if(vecin==tata)
            continue;
        if(v[vecin]==1){
            low[nod]=min(low[nod],NIV[vecin]);
        }
        else{
            dfs(vecin,niv+1,nod);
            low[nod]=min(low[nod],low[vecin]);
            if(low[vecin]>=NIV[nod]){
                componente++;
                F[nod]++;
                do{
                    x=stiva.top();
                    C[componente].push_back(x);
                    stiva.pop();
                }while(x!=vecin);
                C[componente].push_back(nod);

            }
        }
    }
}

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