Cod sursa(job #3227114)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 25 aprilie 2024 15:33:12
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin("biconexe.in");
ofstream cout("biconexe.out");

const int NMAX = 1e5;

int n, m, curent_time, ind;
vector<int> G[NMAX + 1];
int DFS_time[NMAX + 1];
int low[NMAX + 1];
stack<int> st;
vector<int> BCC[NMAX + 1];

void GetBCC(int node, int next_node)
{
    ind++;
    while(st.top() != next_node)
    {
        BCC[ind].push_back(st.top());
        st.pop();
    }
    BCC[ind].push_back(st.top());
    st.pop();
    BCC[ind].push_back(node);
}

void DFS(int node, int dad)
{
    DFS_time[node] = low[node] = ++curent_time;
    st.push(node);
    for(int next_node : G[node])
        if(!DFS_time[next_node])
        {
            DFS(next_node, node);
            low[node] = min(low[node], low[next_node]);
            if(low[next_node] >= DFS_time[node])
                GetBCC(node, next_node);
        }
        else if(next_node != dad)
            low[node] = min(low[node], DFS_time[next_node]);
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(int i = 1; i <= n; i++)
        if(!DFS_time[i])
            DFS(i, 0);

    cout << ind << '\n';
    for(int i = 1; i <= ind; i++, cout << '\n')
        for(int x : BCC[i])
            cout << x << ' ';

    return 0;
}