Cod sursa(job #3306987)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 15 august 2025 23:14:32
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int NMAX = 100001;
vector<vector<int>> compBiconexe;
vector<int> G[NMAX];
int level[NMAX], lmin[NMAX];

void DFS(int root, int parent, vector<int> &S)
{
    level[root] = level[parent] + 1;
    lmin[root] = level[root];
    S.push_back(root);
    for (auto x: G[root])
    {
        if (x == parent)
        {
            continue;
        }
        if (level[x] == 0)
        {
            DFS(x, root, S);
            if (lmin[x] >= level[root])
            {
                vector<int> crtCompBicon;
                while (S.back() != root)
                {
                    crtCompBicon.push_back(S.back());
                    S.pop_back();
                }
                crtCompBicon.push_back(root);
                compBiconexe.push_back(crtCompBicon);
            }
            lmin[root] = min(lmin[root], lmin[x]);
        }
        else
        {
            lmin[root] = min(lmin[root], level[x]);
        }
    }

}

int main()
{
    int n, m;
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        f >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    vector<int> S;
    DFS(1, 0, S);
    g << compBiconexe.size() << '\n';
    for (auto comp: compBiconexe)
    {
        for (auto node: comp)
        {
            g << node << ' ';
        }
        g << '\n';
    }

    return 0;
}