Cod sursa(job #2809063)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 25 noiembrie 2021 21:24:17
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;
const int NMAX = 100000;

int stck[NMAX], sp, lvl[NMAX], maxH[NMAX];
vector<int> edges[NMAX];
vector<vector<int>> bi;

int dfs(int node, int node_lvl)
{
    lvl[node] = node_lvl;
    maxH[node] = node_lvl;
    stck[++sp] = node;
    int len = edges[node].size(), i;
    for (i = 0; i < len; i++)
    {
        if (lvl[edges[node][i]] == 0)
        {
            int aux = dfs(edges[node][i], node_lvl + 1);
            maxH[node] = min(maxH[node], aux);
            if (aux >= node_lvl)
            {
                bi.push_back(vector<int>());
                while (sp >= 0 && stck[sp] != node)
                {
                    bi.back().push_back(stck[sp]);
                    sp--;
                }
                bi.back().push_back(node);
            }
        }
        else
            maxH[node] = min(maxH[node], lvl[edges[node][i]]);
    }
    return maxH[node];
}

int main()
{
    int n, m, v1, v2, i, j, len1, len2;
    FILE *fin = fopen("biconex.in", "r");
    fscanf(fin, "%d%d", &n, &m);

    for (i = 0; i < m; i++)
    {
        fscanf(fin, "%d%d", &v1, &v2);
        v1--, v2--;
        edges[v1].push_back(v2);
        edges[v2].push_back(v1);
    }
    fclose(fin);

    for (i = 0; i < n; i++)
        if (lvl[i] == 0)
            dfs(i, 1);

    FILE *fout = fopen("biconex.out", "w");
    len1 = bi.size();
    fprintf(fout, "%d\n", len1);
    for (i = 0; i < len1; i++)
    {
        len2 = bi[i].size();
        for (j = 0; j < len2; j++)
            fprintf(fout, "%d ", bi[i][j] + 1);
        fprintf(fout, "\n");
    }
    fclose(fout);

    return 0;
}