Cod sursa(job #2618298)

Utilizator adriangh3Adrian Gheorghiu adriangh3 Data 24 mai 2020 16:49:20
Problema Componente biconexe Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.38 kb
#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <stdlib.h>
#include <limits.h>
#include <vector>
#include <unordered_set>

struct Edge
{
    int x, y;
};

void add_nodes(std::unordered_set<int> *set, Edge edge, std::vector<int> *biconex, int *nr)
{
    if (set->find(edge.x) == set->end())
    {
        set->insert(edge.x);
        biconex[*nr].push_back(edge.x);
    }
    if (set->find(edge.y) == set->end())
    {
        set->insert(edge.y);
        biconex[*nr].push_back(edge.y);
    }
}

void dfs(std::vector<int> graph[], int nod, int *disc, int *low, int *time, int *parent, std::stack<Edge> *st, int *nr, std::vector<int> *biconex)
{
    disc[nod] = low[nod] = ++(*time);
    int children = 0;
    for (int k = 0; k < graph[nod].size(); k++)
    {
        int i = graph[nod][k];
        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]))
            {
                std::unordered_set<int> set;
                while (st->top().x != nod || st->top().y != i)
                {
                    add_nodes(&set, st->top(), biconex, nr);
                    st->pop();
                }
                add_nodes(&set, st->top(), biconex, nr);
                st->pop();
                (*nr)++;
            }
        }
        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);
                }
            }
        }
    }
}

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);
    std::vector<int> graph[100000];
    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);
        nod1--;
        nod2--;
        graph[nod1].push_back(nod2);
        graph[nod2].push_back(nod1);
    }
    std::stack<Edge> st;
    int nr = 0;
    std::vector<int> biconex[100000];
    for (int i = 0; i < n; i++)
    {
        if (disc[i] == -1)
        {
            dfs(graph, i, disc, low, &time, parent, &st, &nr, biconex);
            std::unordered_set<int> set;
            int flag = 0;
            while (!st.empty())
            {
                flag = 1;
                add_nodes(&set, st.top(), biconex, &nr);
                st.pop();
            }
            if (flag)
                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]);
        }
        fprintf(out, "\n");
    }
    free(low);
    free(disc);
    free(parent);
    fclose(in);
    fclose(out);
    return 0;
}