Cod sursa(job #2149220)

Utilizator sebastiannrxRichiteanu Mihai Sebastian sebastiannrx Data 2 martie 2018 13:35:50
Problema Componente biconexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
#include <fstream>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
#define nmax 1000005
#define mmax 1000005
int vf,nrf,nr,nrb,pas,cer,n,m,nro[nmax],low[nmax],art[nmax],t[nmax];
struct nod {int x,y;nod *urm;}*a[nmax],*b[nmax],*p;
struct stiva {int x,y;}c[mmax],mm[mmax];
void adaugare (nod*& p,int x) {
    nod *q=new nod;
    q->x=x;
    q->urm=NULL;
    if (p==NULL)
        p=q;
    else {
        nod *nn=p;
        while (nn->urm!=NULL)
            nn=nn->urm;
        nn->urm=q;}}
void read () {
    c[1].x=1;
    c[1].y=-1;
    f>>n>>m;
    int x,y;
    for (int i=1;i<=m;++i) {
        f>>x>>y;
        adaugare(a[x],y);
        adaugare(a[y],x);}
    for (int i=1;i<=n;++i)
        nro[i]=low[i]=-1;}
void muta (int fiu,int x) {
    ++nrb;
    do {
        nod *z=new nod;
        z->x=c[vf].x;
        z->y=c[vf].y;
        z->urm=b[nrb];
        b[nrb]=z;
        --vf;
    }while( !((c[vf+1].y==x && c[vf+1].x==fiu)||(c[vf+1].y==fiu && c[vf+1].x==x)));}
void biconex (int x) {
    nod *q;
    int fiu;
    low[x]=nro[x]=++pas;
    for (q=a[x];q;q=q->urm) {
        fiu=q->x;
        if (fiu!=t[x] && nro[fiu]<nro[x])
            c[++vf].x=fiu,c[vf].y=x;
        if (nro[fiu]==-1) {
            if (x==1)
                ++nrf;
                nro[fiu]=nro[x]+1;
                t[fiu]=x;
            biconex(fiu);
            low[x]=min(low[x],low[fiu]);
            if (low[fiu]>=nro[x]) {
                if (x!=1)
                    art[x]=1;
                muta(fiu,x);}
            }
        else if (fiu!=t[x])
            low[x]=min(nro[fiu], low[x]);}}
void out1 (nod *p, int i) {
    if (p) {
        if(t[p->x]==0)
        ++nr;
        if(t[p->y]==0)
        ++nr;
        t[p->x]=i;
        t[p->y]=i;
        out1(p->urm,i);}}
int main()
{   read();
    nro[1]=1;
    biconex(1);
    g<<nrb<<'\n';
    for (int i=1;i<=nrb;++i) {
        nr=0;
        for(int j=1;j<=n;++j)
            t[j]=0;
        out1(b[i],i);
        for(int j=1;j<=n;++j)
        if(t[j]==i)
        g<<j<<' ';
        g<<'\n';}
    return 0;
}