Cod sursa(job #3302839)

Utilizator Ilinca_Radu_2022Radu Ilinca-Rucsandra Ilinca_Radu_2022 Data 11 iulie 2025 14:30:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#define MAX1 100005
#define MAX2 2*MAX1
#define pereche pair<int, int>
#define fi first
#define se second
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, i, x, y, k, in[MAX1], low[MAX1];
vector<int>v[MAX1];
map<int,int>comp[MAX2];
stack<pereche>s;
void dfs(int nod, int lvl) {
    in[nod]=low[nod]=lvl;
    for (auto x:v[nod]) {
        if (in[x]==0) {
            s.push({nod, x});
            dfs(x, lvl+1);
            low[nod]=min(low[nod], low[x]);
            if (low[x]==in[nod]) {
                k++;
                while (!s.empty()) {
                    pereche y=s.top();
                    s.pop();
                    comp[k][y.fi]=comp[k][y.se]=1;
                    if (y==make_pair(nod, x)) break;
                }
            }
        }
        else low[nod]=min(low[nod], in[x]);
    }
}
int main()
{
    fin>>n>>m;
    for (i=1; i<=m; i++) {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 1);
    fout<<k<<'\n';
    for (i=1; i<=k; i++) {
        for (auto x:comp[i]) fout<<x.fi<<' ';
        fout<<'\n';
    }
    return 0;
}