Cod sursa(job #2169645)

Utilizator dacianouaPapadia Mortala dacianoua Data 14 martie 2018 16:25:13
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.38 kb
#include <iostream>
#include <fstream>
#define nmax 100000
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct nod
{
    int info;
    bool viz;
    nod* urm;
}*v[nmax+5],*c,*e[nmax+5],*sol[nmax+1];
int n,m,disc[nmax+5],low[nmax+5],tata[nmax+5],nrsol=0,time=0,siz=0,st_sol[nmax];
bool viz[nmax+5],mc[nmax+5];
int minv(int a,int b)
{
    return a<b?a:b;
}
void add_sol()
{
    nrsol++;
    sol[nrsol]=new nod;
    sol[nrsol]->info=st_sol[1];
    sol[nrsol]->viz=0;
    sol[nrsol]->urm=0;
    nod *d=sol[nrsol];
    for(int i=2;i<=siz;i++,d=d->urm)
        {
            c=new nod;
            c->info=st_sol[i];
            c->urm=0;
            c->viz=0;
            d->urm=c;
        }
}
void solve(int k)
{
    time++;
    disc[k]=low[k]=time;
    viz[k]=1;
    nod *d=v[k];
    while(d->urm)
    {
        d=d->urm;
        if(!viz[d->info])
        {
            tata[d->info]=k;
            solve(d->info);
            low[k]=minv(low[k],low[d->info]);
            if(low[d->info]>disc[k])
                {
                    ++nrsol;
                    sol[nrsol]=new nod;
                    sol[nrsol]->info=k;
                    sol[nrsol]->viz=0;
                    c=new nod;
                    c->info=d->info;
                    c->urm=0;
                    c->viz=0;
                    sol[nrsol]->urm=c;
                    d->viz=1;
                    nod *g=v[d->info];
                    while(g->urm)
                    {
                        g=g->urm;
                        if(g->info==k)
                        {g->viz=0;break;}
                    }
                }
        }
        else if(d->info!=tata[k])
            low[k]=minv(low[k],disc[d->info]);
    }

}
void dfs(int k)
{
    viz[k]=0;
    nod *d=v[k];
    st_sol[++siz]=k;
    while(d->urm)
    {
        d=d->urm;
        if(viz[d->info] && !d->viz)
            dfs(d->info);
    }
}
int main()
{
    int x,y;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->info=i;
        v[i]->urm=0;
        v[i]->viz=0;
    }
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        if(!v[x]->urm)
        {
            c=new nod;
            c->info=y;
            c->urm=0;
            c->viz=0;
            v[x]->urm=c;
            e[x]=c;
        }
        else
        {
            c=new nod;
            c->info=y;
            c->urm=0;
            c->viz=0;
            e[x]->urm=c;
            e[x]=c;
        }
        if(!v[y]->urm)
        {
            c=new nod;
            c->info=x;
            c->urm=0;
            c->viz=0;
            v[y]->urm=c;
            e[y]=c;
        }
        else
        {
            c=new nod;
            c->info=x;
            c->urm=0;
            c->viz=0;
            e[y]->urm=c;
            e[y]=c;
        }
    }
    for(int i=1;i<=n;i++)
        if(!viz[i])
        solve(i);
    for(int i=1;i<=n;i++)
        if(viz[i])
        {
            siz=0;
            dfs(i);
            if(siz>1)
                add_sol();
        }
    fout<<nrsol<<"\n";
    for(int i=1;i<=nrsol;i++)
    {
        c=sol[i];
        fout<<c->info<<" ";
        while(c->urm)
        {
            c=c->urm;
            fout<<c->info<<" ";
        }
        fout<<"\n";
    }
    return 0;
}