Cod sursa(job #2963199)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 10 ianuarie 2023 11:54:00
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

vector<vector<int> > comp;

vector<int> stk;

const int nmax=100002;
vector<int> adj[nmax];
bool vis[nmax];
int dep[nmax],ret[nmax];

void dfs(int nod, const int par)
{
    ret[nod]=dep[nod]=dep[par]+1;
    vis[nod]=1;
    stk.push_back(nod);
    for(auto e:adj[nod]) if(e!=par)
    {
        //g<<nod<<'-'<<e<<'\n';
        if(vis[e])
        {
            ret[nod]=min(ret[nod],dep[e]);
            continue;
        }
        
        dfs(e,nod);
        
        ret[nod]=min(ret[nod],ret[e]);
        if(ret[e]>=dep[nod])
        {
            comp.push_back(vector<int>());
            while(stk.back()!=e)
            {
                comp.back().push_back(stk.back());
                stk.pop_back();
            }
            stk.pop_back();
            comp.back().push_back(nod);
            comp.back().push_back(e);
        }
    }
    //g<<nod<<','<<ret[nod]<<','<<par<<'\n';
}

int n,m;

int main()
{
    f>>n>>m;
    int a,b;
    for(int i=0;i<m;i++)
    {
        f>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    dfs(1,0);
    g<<comp.size()<<'\n';
    for(auto e:comp)
    {
        for(auto el:e)
        {
            g<<el<<' ';
        }
        g<<'\n';
    }
    return 0;
}