Cod sursa(job #1652295)

Utilizator llalexandruLungu Alexandru Ioan llalexandru Data 14 martie 2016 20:58:54
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <fstream>
#include <algorithm>
#include <stdlib.h>
#define NM 100005

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

struct st{int x, y;};

st Stiva[NM];

int dfn[NM], low[NM], V[NM];

int * A[NM], * Sol[NM];
int n, m, nr, tot;

void Initializare()
{
    int i;
    for (i=1; i<=n; i++)
        dfn[i]=-1;
}

void Afisare(int n, int x)
{
    st p;
    int last, i=0;
    last=0;
    do
    {
        p=Stiva[nr--];
        V[++last]=p.x;
        V[++last]=p.y;
    }while (p.x!=n || p.y!=x);
    sort (V+1, V+last+1);
    tot++;
    Sol[tot]= (int *) realloc(Sol[tot], sizeof(int));
    Sol[tot][0]=0;
    for (i=1; i<=last; i++)
    {
        if (V[i]!=V[i-1])
        {
            Sol[tot][0]++;
            Sol[tot]= (int *) realloc(Sol[tot], (Sol[tot][0]+1)*sizeof(int));
            Sol[tot][Sol[tot][0]]=V[i];
        }
    }
}

void DFS(int n, int mos, int lv)
{
    int i, x;
    dfn[n] = low[n] = lv;
    for (i=1; i<=A[n][0]; i++)
    {
        x=A[n][i];
        if (x==mos) continue;
        if (dfn[x]==-1)
        {
            Stiva[++nr].x=n;
            Stiva[nr].y=x;
            DFS(x, n, lv+1);
            low[n]=min(low[n], low[x]);
            if (low[x]>=dfn[n])
            {
                Afisare(n, x);
            }
        }
        else
            low[n]=min(low[n], dfn[x]);
    }
}

int main()
{
    int i, x, y, j;
    fin>>n>>m;
    Initializare();
    for (i=1; i<=n; i++)
    {
        A[i] = (int *) realloc (A[i], sizeof(int));
        A[i][0]=0;
    }
    for (i=1; i<=m; i++)
    {
        fin>>x>>y;
        A[x][0]++;
        A[x] = (int *) realloc (A[x], (A[x][0]+1)*sizeof(int));
        A[x][A[x][0]]=y;
        A[y][0]++;
        A[y] = (int *) realloc (A[y], (A[y][0]+1)*sizeof(int));
        A[y][A[y][0]]=x;
    }
    DFS(1, 0, 0);
    fout<<tot<<'\n';
    for (i=1; i<=tot; i++)
    {
        for (j=1; j<=Sol[i][0]; j++)
        {
            fout<<Sol[i][j]<<" ";
        }
        fout<<'\n';
    }
    return 0;
}