Cod sursa(job #3041698)

Utilizator pctirziuTirziu Petre pctirziu Data 1 aprilie 2023 10:39:48
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <vector>
#include <stack>

using namespace std;
//ifstream cin("biconex.in");
//ofstream cout("biconex.out");
const int nmax = 1e5 + 5;
stack <int> st;
int parent[nmax], disc[nmax], low[nmax];
int cnt, id;
vector <int> edge[nmax];
vector <int> comp[nmax];
void dfs(int node)
{
    disc[node] = low[node] = ++cnt;
    st.push(node);
    for(int i = 0; i < edge[node].size(); i++){
        int child = edge[node][i];
        if(child == parent[node])
            continue;
        if(disc[child]){
            low[node] = min(low[node], disc[child]);
            continue;
        }
        dfs(child);
        low[node] = min(low[node], low[child]);
        if(low[child] >= disc[node]){
            id++;
            while(st.top() != child){
                comp[id].push_back(st.top());
                st.pop();
            }
            comp[id].push_back(child);
            comp[id].push_back(node);
            st.pop();
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    for(int i = 1; i <= n; i++)
        if(disc[i] == 0){
            cnt = 0;
            dfs(1);
        }
    cout << id << "\n";
    for(int i = 1; i <= id; i++){
        for(int j = 0; j < comp[i].size(); j++)
            cout << comp[i][j] << " ";
        cout << "\n";
    }
    return 0;
}