Cod sursa(job #2824546)

Utilizator NeuerRaducu Ioan Stefan Neuer Data 2 ianuarie 2022 16:42:08
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
///#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <cmath>

using namespace std;
const int SIZE = 1e5+10;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

struct edge
{
    int y, x;
};

int n, m;
vector <int> v[SIZE];
vector <edge> stck;
set <int> comp[SIZE];
int dfn[SIZE], low[SIZE];
int cnt, nrfii, ncnt;

void readit()
{
    stck.push_back({0, 1});
    int y, x;
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>y>>x;
        v[y].push_back(x);
        v[x].push_back(y);
    }
}

void compcon(edge ed)
{
    ++ncnt;
    edge p = stck.back();
    while(p.y!=ed.y || p.x!=ed.x) {
        comp[ncnt].insert(p.y);
        comp[ncnt].insert(p.x);
        stck.pop_back();
        p = stck.back();
    }
    comp[ncnt].insert(p.y);
    comp[ncnt].insert(p.x);
    stck.pop_back();
}

void dfs(int nod, int tnod)
{
    dfn[nod] = low[nod] = ++cnt;
    for(auto nxt : v[nod])
    {
        if(nxt!=tnod && dfn[nxt]<dfn[nod])
            stck.push_back({nod, nxt});
        if(!dfn[nxt])
        {
            dfs(nxt, nod);
            low[nod] = min(low[nod], low[nxt]);
            if(dfn[nod]<=low[nxt]) {
                compcon({nod, nxt});
            }
        }
        else if(nxt!=tnod)
            low[nod] = min(low[nod], dfn[nxt]);
    }
}

int main()
{
    readit();
    dfs(1, 0);
    cout<<ncnt<<'\n';
    for(int i=1; i<=ncnt; i++) {
        for(auto j : comp[i])
            cout<<j<<' ';
        cout<<'\n';
    }
    return 0;
}