Cod sursa(job #2963188)

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

using namespace std;

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

vector<vector<int> > comp;

stack<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(nod);
    for(auto e:adj[nod]) if(e!=par)
    {
        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])
        {
            vector<int> aux;
            while(stk.top()!=nod)
            {
                aux.push_back(stk.top());
                stk.pop();
            }
            aux.push_back(nod);
            comp.push_back(aux);
        }
    }
}

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;
}