Cod sursa(job #2538421)

Utilizator mihaela.macarie01@yahoo.comMihaela Macarie [email protected] Data 4 februarie 2020 18:52:26
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 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 comp(int nod,int fiu)
{
    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 dfs(int nod,int nivel)
{
    viz[nod]=1;
    int fiu;
    niv[nod]=low[nod]=nivel;
    s[++nn]=nod;
    for(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,nivel+1);
        low[nod]=min(low[nod],low[fiu]);
        if(niv[nod]<=low[fiu])
            sol++,comp(nod,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();
    for(i=1;i<=n;i++)
        if(!viz[i])
            t[i]=0,dfs(1,0);
    afisare();
    x.close();
    y.close();
    return 0;
}