Cod sursa(job #1963631)

Utilizator miruna999Morarasu Miruna miruna999 Data 12 aprilie 2017 17:46:08
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct nod{int nr;nod *urm;}*a[100001];
int n,m,critic[100001],low[100001],tata[100001],dfn[100001],radacina,nrr,nrcomp,j;
struct el{int u,tu;};
stack<el>S;
int co[100001],vf[200001];
set<int>comp;
set<int>::iterator it;
bool viz[100001];

void adaug(int x,int y)
{
    nod *p;
    p=new nod;
    p->nr=y;
    p->urm=a[x];
    a[x]=p;
}

void elim(int k,int vecin)
{
    el p;
    do{
        p=S.top();
        comp.insert(p.u);
        comp.insert(p.tu);
        S.pop();
    }while(p.u!=k || p.tu!=vecin);
    for(it=comp.begin();it!=comp.end();it++)
        co[nrcomp]++,vf[++j]=*it;
    comp.clear();
}

void df(int k)
{
    viz[k] = 1;
    low[k]=dfn[k];
    nod *p=a[k];
    while(p)
    {
        int vecin=p->nr;
        if(!viz[vecin])
        {
            dfn[vecin]=dfn[k]+1;
            tata[vecin]=k;
            if(k == radacina)
                nrr++;
            if(vecin!=tata[k] && !viz[vecin])
                S.push({k,vecin});
            df(vecin);
            if(low[k]>low[vecin])
                low[k]=low[vecin];
            if(low[vecin] >= dfn[k])
                nrcomp++,elim(k,vecin),critic[k]=1;
        }
        else
        if(vecin != tata[k] && low[k] > dfn[vecin])
            low[k] = dfn[vecin];
        p=p->urm;
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        f>>x>>y;
        adaug(x,y);
        adaug(y,x);
    }
    for(int i=1;i<=n;i++)
        if(!viz[i])
        {
            S.push({i,-1});
            dfn[i]=1;
            radacina=i;
            nrr=0;
            df(i);
            if (nrr>1)
                critic[radacina]=1;
            else
                critic[radacina]=0;
        }
    g<<nrcomp<<'\n';j=1;
    for(int i=1;i<=nrcomp;++i)
    {
        for(int k=1;k<=co[i];++k,++j)
            g<<vf[j]<<" ";
        g<<'\n';
    }
    return 0;
}