Cod sursa(job #3192683)

Utilizator aaagabiTurbinca Gabriel aaagabi Data 13 ianuarie 2024 10:12:15
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
typedef long long ll;
typedef long double ld;
vector <int> v[100005];
int tin[100005],low[100005];
int viz[100005];
int n,m;
int root;
vector <int> stiva;
vector <int> comp;
vector<vector <int>> biconexe;

void dfs(int nod,int par)
{
    stiva.push_back(nod);
    viz[nod]=1;
    tin[nod]=tin[par]+1;
    low[nod]=tin[nod];
    for(auto x:v[nod])
        if(x!=par)
        {
            if(viz[x]==1)
            {
                low[nod]=min(low[nod],tin[x]);
            }
            else
            {
                dfs(x,nod);
                low[nod]=min(low[nod],low[x]);
            if(tin[nod]<=low[x])
            {
                comp.clear();
                while(stiva[stiva.size()-1]!=x)
                {
                    comp.push_back(stiva[stiva.size()-1]);
                    stiva.pop_back();
                }
                comp.push_back(x);
                stiva.pop_back();
                comp.push_back(nod);
                biconexe.push_back(comp);
            }
            }
        }
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
            dfs(i,0);
    fout<<biconexe.size()<<'\n';
    for(int i=0;i<biconexe.size();i++)
    {
        for(int j=0;j<biconexe[i].size();j++)
            fout<<biconexe[i][j]<<' ';
        fout<<'\n';
    }
    return 0;
}