Cod sursa(job #3349203)

Utilizator dragutamihai1234Draguta Mihai dragutamihai1234 Data 26 martie 2026 10:56:18
Problema Componente biconexe Scor 76
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

const int NMAX = 1e5 + 1;

struct node
{
    int tin, low;
} nd[NMAX];

int n, m;
struct connected_components
{
    set<int> C;
} v[NMAX];

vector<int> G[NMAX];
int p[NMAX];

struct muchie
{
    int x, y;
} st[NMAX];
int vf;
int cmp;

void pop_bcc(int x, int y)
{
    cmp++;
    while (st[vf].x != x && st[vf].y != y)
    {
        v[cmp].C.insert(st[vf].x);
        v[cmp].C.insert(st[vf].y);
        vf--;
    }
    v[cmp].C.insert(st[vf].x);
    v[cmp].C.insert(st[vf].y);
    vf--;
}

void dfs(int node, int parent)
{
    static int timp = 0;
    nd[node].tin = nd[node].low = ++timp;
    for (int to : G[node])
    {
        if (!nd[to].tin) /// e nevizitat
        {
            st[++vf] = {node, to};
            dfs(to, node);
            nd[node].low = min(nd[node].low, nd[to].low);
            if (nd[node].tin <= nd[to].low)
                pop_bcc(node, to);
        }
        else if (to != parent)
        {
            if (nd[to].tin < nd[node].tin) /// muchie inapoi
            {
                st[++vf] = {node, to};
                nd[node].low = min(nd[node].low, nd[to].tin);
            }
        }
    }
}
void read()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        f >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
}
void afis()
{
    g << cmp << '\n';
    for (int i = 1; i <= cmp; i++)
    {
        for (auto it = v[i].C.begin(); it != v[i].C.end(); it++)
            g << (*it) << ' ';
        g << '\n';
    }
}

int main()
{
    read();
    dfs(1, 0);
    afis();
    return 0;
}