Cod sursa(job #3198480)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 29 ianuarie 2024 16:53:36
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 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, int nxt){
    vector <int> bicon;
    while( !sol.empty() && sol.top() != nxt ){
        bicon.push_back(sol.top());
        sol.pop();
    }
    sol.pop();
    bicon.push_back(nxt);
    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, next);

        }
        else
            highest[node] = min(depth[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);
    }
    for( int i = 1; i <= n; i++ )
        if( !depth[i] )
            tarjan( i, 1, i);

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