Cod sursa(job #2884554)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 3 aprilie 2022 23:59:06
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
ifstream in("biconexe.in");
ofstream out("biconexe.out");
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()
{
    int n,i,m,a,b;
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=1; i<=n; i++)
        if(!viz[i])
            dfs(i,0);
    out<<ans.size()<<'\n';
    for(auto it:ans)
    {
        for(auto it1:it)

            out<<it1<<" ";
        out<<'\n';
    }
    return 0;
}