Cod sursa(job #2538545)

Utilizator mihaela.macarie01@yahoo.comMihaela Macarie [email protected] Data 4 februarie 2020 20:29:19
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 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,viz[N];
int *a[N],*b[N],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 dfs(int nod)
{
    int fiu;
    viz[nod]=1;
    niv[nod]=low[nod]=niv[t[nod]]+1;
    s[++nn]=nod;
    for(int j=1;j<=a[nod][0];j++)
    {
        fiu=a[nod][j];
        if(viz[fiu])
        {
            if(fiu!=t[nod])
                low[nod]=min(low[nod],niv[fiu]);
            continue;
        }
        t[fiu]=nod;
        dfs(fiu);
        low[nod]=min(low[fiu],low[nod]);
        if(niv[nod]<=low[fiu])
        {
            sol++;
            b[sol]=(int *)realloc(b[sol],sizeof(int));
            b[sol][0]=0;
            do
            {
                k=s[nn];
                b[sol][0]++;
                b[sol]=(int *)realloc(b[sol],(b[sol][0]+1)*sizeof(int));
                b[sol][b[sol][0]]=k;
                nn--;
            }while(k!=fiu);
            b[sol][0]++;
            b[sol]=(int *)realloc(b[sol],(b[sol][0]+1)*sizeof(int));
            b[sol][b[sol][0]]=nod;
        }
    }
}
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();
    for(i=1;i<=n;i++)
        if(!viz[i])
            t[i]=0,dfs(i);
    afisare();
    x.close();
    y.close();
    return 0;
}