Cod sursa(job #2884553)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 3 aprilie 2022 23:57:58
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;
vector <int> v[100001];
vector <int> vec;
int low[100001],niv[100001];
bool viz[100001];
int cnt;
int steve[100001],vf;
vector <vector<int>> ans;
void dfs(int nod,int papa)
{
    viz[nod]=1;
    niv[nod]=low[nod]=1+niv[papa];
    steve[++vf]=nod;
    for(auto it:v[nod])
        if(viz[it])
            low[nod]=min(low[nod],niv[it]);
        else
        {
            dfs(it,nod);
            low[nod]=min(low[nod],low[it]);
            if(low[it]==niv[nod])
            {
                ans.push_back({nod,it});
                while(vf&&steve[vf]!=it)
                    ans.back().push_back(steve[vf--]);
                vf--;
            }
        }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int n,i,m,a,b;
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=1; i<=n; i++)
        if(!viz[i])
            dfs(i,0);
    cout<<ans.size()<<'\n';
    for(auto it:ans)
    {
        for(auto it1:it)
            cout<<it1<<" ";
        cout<<'\n';
    }
    return 0;
}