Cod sursa(job #2668587)

Utilizator marian222200Dimofte Marian marian222200 Data 5 noiembrie 2020 02:02:44
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#define N 100001
#include<fstream>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct nod{
    nod *urm;
    int info;
};
int nrstiva;
int stiva[N];

nod *l[N];
int n,m;

nod *sol[N];
int nrsol;

int viz[N];
int niv[N],up[N];
void citire(){
    int x,y,i;
    nod *p;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        p =new nod;
        p->info=y;
        p->urm=l[x];
        l[x]=p;

        p=new nod;
        p->info=x;
        p->urm=l[y];
        l[y]=p;
    }
}
void dfs(int x,int tata){
    nod *p,*q;

    viz[x]=1;
    up[x]=niv[x];
    stiva[++nrstiva]=x;

    for(p=l[x];p!=NULL;p=p->urm){

        if(p->info==tata)continue;

        if(viz[p->info])up[x]=min(up[x],niv[p->info]);

        else{
            niv[p->info]=niv[x]+1;
            dfs(p->info,x);
            if(up[p->info]>=niv[x]){
                nrsol++;
                while(nrstiva&&stiva[nrstiva]!=p->info){
                    q=new nod;
                    q->info=stiva[nrstiva--];
                    q->urm=sol[nrsol];
                    sol[nrsol]=q;
                }
                q=new nod;
                q->info=stiva[nrstiva--];
                q->urm=sol[nrsol];
                sol[nrsol]=q;

                q=new nod;
                q->info=x;
                q->urm=sol[nrsol];
                sol[nrsol]=q;
            }
            up[x]=min(up[x],up[p->info]);
        }
    }
}
void afisare(){
    nod *p;
    int i;
    fout<<nrsol<<"\n";
    for(i=1;i<=nrsol;i++){
        p=sol[i];
        while(p!=NULL){
            fout<<p->info<<" ";
            p=p->urm;
        }
        fout<<"\n";
    }
}
int main(){
    citire();
    dfs(1,0);
    afisare();
    return 0;
}