Cod sursa(job #2927921)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 21 octombrie 2022 20:19:39
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int maxn = 100005;
vector <int> bicon[maxn];
vector <int> v[maxn];
stack <int> stk;
int minback[maxn];
int niv[maxn];

int conexe;

void dfs(int nod, int tata)
{
    stk.push(nod);
    for(auto it : v[nod])
    {
        if(niv[it] == 0) /// acum sunt la un vecin necalculat
        {
            niv[it] = niv[nod] + 1;
            minback[it] = niv[nod] + 1;
            int bef = stk.size();
            dfs(it, nod);
            minback[nod] = min(minback[nod], minback[it]);
            if(minback[it] >= niv[nod]) /// componenta biconexa noua
            {
                conexe++;
                bicon[conexe].push_back(nod);
                while(stk.size() > bef)
                {
                    bicon[conexe].push_back(stk.top());
                    stk.pop();
                }
            }
        }
        else if(it != tata)
            minback[nod] = min(minback[nod], niv[it]);
    }
}

int main()
{
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    niv[1] = 1;
    dfs(1, 0);
    /*
    for(int i = 1; i <= n; i++)
        cerr << niv[i] << " ";
    cerr << "\n";
    for(int i = 1; i <= n; i++)
        cerr << minback[i] << " ";
    cerr << "\n";
    */
    out << conexe << "\n";
    for(int i = 1; i <= conexe; i++, out << "\n")
        for(auto it : bicon[i])
            out << it << " ";
    return 0;
}