Cod sursa(job #3200136)

Utilizator Dragu_AndiDragu Andrei Dragu_Andi Data 3 februarie 2024 16:50:43
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int n, m;
int ord[100001], up[100001];
bool used[100001];
vector <int> stiva, curr_comp, G[100001];
vector <vector <int>> all_comps;

int cnt=0;
void dfs(int nod, int tata)
{
    stiva.push_back(nod);
    used[nod]=1;
    up[nod]=nod;
    ord[nod]=++cnt;
    for(int fiu: G[nod])
    {
        if(fiu==tata) continue;
        if(used[fiu])
        {
            up[nod]=min(up[nod],ord[fiu]);
            continue;
        }
        dfs(fiu, nod);
        if(ord[nod]<=up[fiu])
        {
            while(stiva.back()!=fiu)
            {
                curr_comp.push_back(stiva.back());
                stiva.pop_back();
                curr_comp.push_back(fiu);
                curr_comp.push_back(nod);
                all_comps.push_back(curr_comp);
                curr_comp.clear();
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i = 1; i <= n; i++)
        if(!used[i])
            dfs(i, 0);
    fout << all_comps.size() << '\n';
    for(auto c : all_comps)
    {
        for(int x : c)
            fout << x << ' ';
        fout << '\n';
    }
    return 0;
}