Cod sursa(job #2537848)

Utilizator mihaela.macarie01@yahoo.comMihaela Macarie [email protected] Data 4 februarie 2020 00:13:01
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#define N 100002

using namespace std;

ifstream x("biconex.in");
ofstream y("biconex.out");

int n,m,i,j,k;
int niv[N],low[N],t[N],nn,nivel,sol;
int *a[N],*b[N];

struct elem
{
    int l,c;
}s[N];

void citire()
{
    x>>n>>m;
    for(i=1;i<=n;i++)
    {
        a[i]=(int *) realloc(a[i],sizeof(int));
        a[i][0]=0;
    }
    for(k=1;k<=m;k++)
    {
        x>>i>>j;
        a[i][0]++;
        a[i]=(int *) realloc(a[i],(a[i][0]+1)*sizeof(int));
        a[i][a[i][0]]=j;
        a[j][0]++;
        a[j]=(int *) realloc(a[j],(a[j][0]+1)*sizeof(int));
        a[j][a[j][0]]=i;
    }
}

void componenta(int st, int dr)
{
    int ii,jj;
    sol++;
    b[sol]=(int *) realloc(b[sol],sizeof(int));
    b[sol][0]=0;
    do
    {
        ii=s[nn].l;
        jj=s[nn].c;
        nn--;
        b[sol][0]++;
        b[sol]=(int *)realloc(b[sol],(b[sol][0]+1)*sizeof(int));
        b[sol][b[sol][0]]=jj;
    }while(ii!=st && jj!=dr);
    b[sol][0]++;
    b[sol]=(int *)realloc(b[sol],(b[sol][0]+1)*sizeof(int));
    b[sol][b[sol][0]]=st;
}

void dfs(int nod,int nivel)
{
    int fiu;
    niv[nod]=low[nod]=nivel;
    for(j=1;j<=a[nod][0];j++)
    {
        fiu=a[nod][j];
        if(fiu!=t[nod])
        {
            if(!niv[fiu])
            {
                nn++;
                s[n].l=nod;
                s[nn].c=fiu;
                t[fiu]=nod;
                dfs(fiu,nivel+1);
                if(low[fiu]>=niv[nod])
                    componenta(nod,fiu);
                low[nod]=min(low[nod],low[fiu]);
            }
            else
                low[nod]=min(low[nod],niv[fiu]);
        }
    }
}
void afisare()
{
    y<<sol<<'\n';
    for(i=1;i<=sol;i++)
    {
        for(j=1;j<=b[i][0];j++)
            y<<b[i][j]<<" ";
        y<<'\n';
    }
}

int main()
{
    citire();
    dfs(1,0);
    afisare();
    x.close();
    y.close();
    return 0;
}