Cod sursa(job #2836421)

Utilizator rapidu36Victor Manz rapidu36 Data 20 ianuarie 2022 12:48:07
Problema Componente biconexe Scor 80
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <stdio.h>
#include <stdlib.h>
#define N 100000
#define M 200000

typedef struct
{
    int vf, urm;
} element;

int lst[N+1], t[N+1], tmin[N+1], stiva[N+1], nr, n, m, timp, vf, lst_cbc[N+1], n_cbc;
element v[2*M+1], cbc[N+1];

void adauga(int x, int y)
{
    v[++nr].vf = y;
    v[nr].urm = lst[x];
    lst[x] = nr;
}

void adauga_cbc(int c, int x)
{
    cbc[++nr].vf = x;
    cbc[nr].urm = lst_cbc[c];
    lst_cbc[c] = nr;
}

void biconex(int y, int x)
{
    n_cbc++;
    while (vf != 0 && stiva[vf] != y)
    {
        //printf("%d ", stiva[vf]);
        adauga_cbc(n_cbc, stiva[vf]);
        vf--;
    }
    //printf("%d ", stiva[vf]);
    adauga_cbc(n_cbc, stiva[vf]);
    vf--;
    //printf("%d\n", x);
    adauga_cbc(n_cbc, x);
}

void dfs(int x, int tata)
{
    tmin[x] = t[x] = ++timp;
    stiva[++vf] = x;
    for (int p = lst[x]; p != 0; p = v[p].urm)
    {
        int y = v[p].vf;
        if (y == tata)
        {
            continue;
        }
        if (t[y] == 0)
        {
            dfs(y, x);
            if (tmin[y] < tmin[x])
            {
                tmin[x] = tmin[y];
            }
            if (tmin[y] >= t[x])
            {
                biconex(y, x);
            }
        }
        else
        {
            if (t[y] < tmin[x])
            {
                tmin[x] = t[y];
            }
        }
    }
}

int main()
{
    FILE *in, *out;
    in = fopen("biconex.in", "r");
    out = fopen("biconex.out", "w");
    fscanf(in, "%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        fscanf(in, "%d%d", &x, &y);
        adauga(x, y);
        adauga(y, x);
    }
    fclose(in);
    nr = 0;
    for (int i = 1; i <= n; i++)
    {
        if (t[i] == 0)
        {
            dfs(i, 0);
        }
    }
    fprintf(out, "%d\n", n_cbc);
    for (int i = 1; i <= n_cbc; i++)
    {
        for (int p = lst_cbc[i]; p != 0; p = cbc[p].urm)
        {
            fprintf(out, "%d ", cbc[p].vf);
        }
        fprintf(out, "\n");
    }
    fclose(out);
    return 0;
}