Cod sursa(job #3275224)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 9 februarie 2025 14:52:03
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <vector>
#include <set>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int N=2e5+1;
vector<int>adj[N];
vector<set<int>>comp(N);
int n,m;
stack<pair<int,int>>st;
int height[N],low[N];
int cnt=0;
bool viz[N];
void sterge(int a,int b)
{
    cnt++;
    int tx=-1,ty=-1;
    do
    {
        tx=st.top().first;
        ty=st.top().second;
        st.pop();
        comp[cnt].insert(tx);
        comp[cnt].insert(ty);
    }
    while(tx!=a&&ty!=b);
}
void dfs(int nod,int p)
{
    viz[nod]=true;
    height[nod]=height[p]+1;
    low[nod]=height[nod];
    for(auto u:adj[nod])
    {
        if(u==p)
            continue;
        if(viz[u]==true)
        {
            low[nod]=min(low[nod],height[u]);
        }
        else
        {
            st.push({nod,u});
            dfs(u,nod);
            if(low[u]>=height[nod])
            {
                sterge(nod,u);
            }
            low[nod]=min(low[nod],low[u]);
        }
    }

}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,0);
    cout<<cnt<<'\n';
    for(int i=1;i<=cnt;i++)
    {
        for(auto u:comp[i])
            cout<<u<<" ";
        cout<<'\n';
    }
    return 0;
}