Cod sursa(job #3219806)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 1 aprilie 2024 12:26:02
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int N = 1e5;

int dist[N + 10], viz[N + 10], distMin[N + 10];

vector <int> g[N + 10];
vector <int> bi[N + 10];
stack <int> st;

int comp;

void dfs (int node, int par ) {
    
    st.push(node);
    
    dist[node] = dist[par] + 1;
    distMin[node] = dist[node];
    viz[node] = 1;
    
    for ( int i = 0; i < g[node].size(); i++ ) {
        
        if ( g[node][i] != par ) {
            
            if ( viz[g[node][i]] == 0 ) {
                
                dfs ( g[node][i], node );
                
                distMin[node] = min ( distMin[node], distMin[g[node][i]] );
                
                if ( distMin[g[node][i]] >= dist[node] ) {
                    
                    comp++;
                    
                    while ( !st.empty() && st.top() != g[node][i] ) {
                        bi[comp].push_back( st.top() );
                        st.pop();
                    }
                    
                    bi[comp].push_back (st.top());
                    st.pop();
                    bi[comp].push_back (node);
                }
            }
            
            else
                distMin[node] = min ( distMin[node], dist[g[node][i]] );
        }
    }
}
    
int main () {
    
    int n, m, x, y;
    
    fin >> n >> m;
    
    for ( int i = 0; i < m; i++ ) {
        
        fin >> x >> y;
        
        g[x].push_back(y);
        g[y].push_back(x);
    }
    
    dfs(1, 0);
    
    fout << comp << "\n";
    
    for ( int i = 1; i <= comp; i++ ) {
        for ( int j = 0; j < bi[i].size(); j++ )
            fout << bi[i][j] << " ";
        fout << "\n";
    }
    
    return 0;
}