Cod sursa(job #3198478)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 29 ianuarie 2024 16:36:50
Problema Componente biconexe Scor 42
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int NMAX = 100005;
const int MMAX = 200005;
stack <int> sol;
vector <vector <int>> afis;
vector <int> g[NMAX];
int highest[NMAX];
int depth[NMAX];
void build( int node){
    vector <int> bicon;
    while( !sol.empty() && sol.top() != node ){
        bicon.push_back(sol.top());
        sol.pop();
    }
    bicon.push_back(node);
    afis.push_back(bicon);
}
void tarjan( int node, int level, int tata ){
    sol.push(node);
    highest[node] = level;
    depth[node] = level;
    for( auto next : g[node] ){
        if( next == tata )
            continue;
        if( !depth[next] ){
            tarjan(next, level+1, node);
            highest[node] = min(highest[next], highest[node]);
            if( highest[next] >= level ) {
                build(node);
//                cout << node << ' ';
            }
        }
        else
            highest[node] = min(highest[next], highest[node]);
    }
}
int main()
{
    int n, m;
    in >> n >> m;
    for( int i = 0; i < m; i++ ){
        int a, b;
        in >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    tarjan( 1, 1, 0);
//    for (int i = 1; i <= n; i++) {
//        cout << highest[i] << ' ';
//    }
//    cout << '\n';

    out << afis.size() << "\n";
    for( int i = 0; i < afis.size() ; i++ ){
        for( int node: afis[i] )
            out << node << " ";
        out << "\n";
    }
    return 0;
}