Cod sursa(job #3372371)

Utilizator GrigoreAlexandraGrigore Alexandra GrigoreAlexandra Data 3 noiembrie 2026 13:27:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 kb
//O(n+m)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int NMAX = 100005;

struct Muchie
{
    int x, y;
};

vector<int> adj[NMAX];
int tin[NMAX], low[NMAX];
int timp = 0;

stack<Muchie> stiva;
vector<vector<int>> componente;

void dfs(int nod, int parinte)
{
    tin[nod] = low[nod] = ++timp;

    for (int vecin : adj[nod])
    {
        if (vecin == parinte)
            continue;

        if (tin[vecin] == 0)
        {
            stiva.push({nod, vecin});

            dfs(vecin, nod);

            low[nod] = min(low[nod], low[vecin]);

            if (low[vecin] >= tin[nod])
            {
                vector<int> comp;

                while (!stiva.empty())
                {
                    Muchie muchie = stiva.top();
                    stiva.pop();

                    comp.push_back(muchie.x);
                    comp.push_back(muchie.y);

                    if (muchie.x == nod && muchie.y == vecin)
                        break;
                }

                sort(comp.begin(), comp.end());

                vector<int> faraDuplicate;

                for (int i = 0; i < (int)comp.size(); i++)
                {
                    if (i == 0 || comp[i] != comp[i - 1])
                        faraDuplicate.push_back(comp[i]);
                }

                comp = faraDuplicate;

                componente.push_back(comp);
            }
        }
        else if (tin[vecin] < tin[nod])
        {
            stiva.push({nod, vecin});
            low[nod] = min(low[nod], tin[vecin]);
        }
    }
}

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

    int n, m;
    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 (tin[i] == 0)
            dfs(i, 0);
    }

    fout << componente.size() << '\n';

    for (vector<int> comp : componente)
    {
        for (int nod : comp)
            fout << nod << " ";

        fout << '\n';
    }

    return 0;
}