Cod sursa(job #2667871)

Utilizator paulconst1Constantinescu Paul paulconst1 Data 4 noiembrie 2020 00:05:39
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

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

#define cin fin
#define cout fout

#define Nmax 100010

int n;
vector < int > g[Nmax];
int sus[Nmax], jos[Nmax];

int nr = 0;
vector < int > componente[Nmax];

stack < pair < int, int > > s;

void read() {
    int m;
    cin >> n >> m;
    while(m--) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void scoateStiva(int x, int y) {
    nr++;

    int tx, ty;

    do {
        tx = s.top().first;
        ty = s.top().second;
        s.pop();
        componente[nr].push_back(tx);
        componente[nr].push_back(ty);
    } while (tx != x || ty != y);
}

void DFS(int nod, int tata, int nivel) {

    sus[nod] = jos[nod] = nivel;

    for(const auto it : g[nod] ) {
        if(it == tata) {
            continue;
        }

        if(sus[it] == -1) {
            s.push({nod, it});

            DFS(it, nod, nivel+1);

            jos[nod] = min(jos[nod], jos[it]);

            if(jos[it] >= sus[nod]) {
                scoateStiva(nod, it);
            }
        } else {

            jos[nod] = min(jos[nod], sus[it]);
        }
    }
}

void solve() {
    for(int i=1; i<=n; i++) {
        sus[i] = -1;
    }

    DFS(1, 0, 0);

    cout << nr << endl;

    for(int i=1; i <= nr; i++) {
        sort(componente[i].begin(), componente[i].end());
        componente[i].erase(unique(componente[i].begin(), componente[i].end()), componente[i].end());
        for(const auto it : componente[i]) {
            cout << it << " ";
        }
        cout << endl;
    }
}

int main () {

    read();
    solve();
}