Cod sursa(job #2618268)

Utilizator adriangh3Adrian Gheorghiu adriangh3 Data 24 mai 2020 15:53:42
Problema Componente biconexe Scor 58
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.33 kb
#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <stdlib.h>
#include <limits.h>
#include <vector>

struct gList
{
    int nod, cost;
    struct gList *next;
};

struct Graph
{
    gList **adj;
    int n;
};

struct Edge
{
    int x, y;
};

Graph *init_graph(int n)
{
    Graph *graph = (Graph *)malloc(sizeof(Graph));
    graph->adj = (gList **)calloc(n, sizeof(gList *));
    graph->n = n;
    return graph;
}

void add_arc(Graph *graph, int nod1, int nod2, int cost)
{
    gList *nou = (gList *)malloc(sizeof(gList));
    nou->cost = cost;
    nou->nod = nod2;
    nou->next = graph->adj[nod1];
    graph->adj[nod1] = nou;
}

void free_graph(Graph *graph)
{
    int i;
    for (i = 0; i < graph->n; i++)
    {
        gList *p = graph->adj[i];
        while (p)
        {
            gList *todel = p;
            p = p->next;
            free(todel);
        }
    }
    free(graph->adj);
    free(graph);
}

int get_cost(Graph *graph, int nod1, int nod2)
{
    gList *p = graph->adj[nod1];
    while (p)
    {
        if (p->nod == nod2)
            return p->cost;
        p = p->next;
    }
    return INT_MAX;
}

void dfs(Graph *graph, int nod, int *disc, int *low, int *time, int *parent, std::stack<Edge> *st, int *nr, std::vector<int> *biconex)
{
    gList *p = graph->adj[nod];
    disc[nod] = low[nod] = ++(*time);
    //printf("%d\n", *time);
    int children = 0;
    while (p)
    {
        int i = p->nod;
        if (disc[i] == -1)
        {
            parent[i] = nod;
            children++;
            Edge aux;
            aux.x = nod;
            aux.y = i;
            st->push(aux);
            dfs(graph, i, disc, low, time, parent, st, nr, biconex);
            low[nod] = std::min(low[nod], low[i]);
            if ((disc[nod] == 1 && children > 1) ||
                (disc[nod] > 1 && low[i] >= disc[nod]))
            {
                int flag = 0;
                while (st->top().x != nod || st->top().y != i)
                {
                    flag = 1;
                    biconex[*nr].push_back(st->top().x);
                    st->pop();
                }
                if (flag)
                {
                    //printf("%d\n", st->top().x + 1);
                    biconex[(*nr)++].push_back(st->top().x);
                }
                else
                {
                    printf("%d %d\n", st->top().x + 1, st->top().y + 1);
                    biconex[*nr].push_back(st->top().x);
                    biconex[(*nr)++].push_back(st->top().y);
                }
                st->pop();
            }
        }
        else
        {
            if (i != parent[nod])
            {
                low[nod] = std::min(low[nod], disc[i]);
                if (disc[i] < disc[nod])
                {
                    Edge aux;
                    aux.x = nod;
                    aux.y = i;
                    st->push(aux);
                }
            }
        }
        p = p->next;
    }
}

int main()
{
    FILE *in = fopen("biconex.in", "r");
    FILE *out = fopen("biconex.out", "w");
    int n, m;
    fscanf(in, "%d", &n);
    fscanf(in, "%d", &m);
    Graph *graph = init_graph(n);
    int *low = (int *)malloc(n * sizeof(int));
    int *disc = (int *)malloc(n * sizeof(int));
    int *parent = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
        disc[i] = parent[i] = low[i] = -1;
    int time = 0;
    for (int i = 0; i < m; i++)
    {
        int nod1, nod2;
        fscanf(in, "%d%d", &nod1, &nod2);
        //printf("%d %d\n", nod1, nod2);
        nod1--;
        nod2--;
        add_arc(graph, nod1, nod2, 1);
        add_arc(graph, nod2, nod1, 1);
    }
    std::stack<Edge> st;
    int nr = 0;
    std::vector<int> biconex[100000];
    dfs(graph, 0, disc, low, &time, parent, &st, &nr, biconex);
    if (st.size() == 1)
    {
        biconex[nr].push_back(st.top().x);
        biconex[nr].push_back(st.top().y);
    }
    else
    {
        while (!st.empty())
        {
            biconex[nr].push_back(st.top().x);
            st.pop();
        }
    }
    nr++;
    fprintf(out, "%d\n", nr);
    for (int i = 0; i < nr; i++)
    {
        for (int j = 0; j < biconex[i].size(); j++)
        {
            fprintf(out, "%d ", biconex[i][j] + 1);
        }
        fprintf(out, "\n");
    }
    free(low);
    free(disc);
    free(parent);
    free_graph(graph);
    fclose(in);
    fclose(out);
    return 0;
}