Cod sursa(job #3292683)

Utilizator Mihai_999Diaconeasa Mihai Mihai_999 Data 8 aprilie 2025 22:53:53
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nl '\n'

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

const int NMAX = 1e5+5;

int n, m, cb, fr[NMAX], ord[NMAX], low[NMAX], k, st[NMAX], top;
vector<int> adj[NMAX], comp[NMAX];

void dfs(int i, int p)
{
    fr[i] = 1;
    st[++top] = i;
    ord[i] = low[i] = ++k;
    for (int j : adj[i])
    {
        if (j == p)
            continue;
        if (fr[j])
            low[i] = min(low[i], ord[j]);
        else
        {
            dfs(j, i);
            low[i] = min(low[i], low[j]);
            if (low[j] >= ord[i]) /// i nod critic
            {
                cb++;
                while (st[top] != j)
                    comp[cb].push_back(st[top--]);
                comp[cb].push_back(j);
                top--;
                comp[cb].push_back(i);
            }
        }
    }
    return;
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
        if (!fr[i])
            dfs(i, 0);
    fout << cb << nl;
    for (int i = 1; i <= cb; i++)
    {
        for (int j : comp[i])
            fout << j << ' ';
        fout << nl;
    }
    return 0;
}