Cod sursa(job #2920857)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 26 august 2022 14:00:38
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
#define vec vector<int>
#define nmax 100001
using namespace std;

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

vec adj[nmax];
vec stk;

vector< vec > c;

int h[nmax],low[nmax];
int n,m;
void addcmp(const int &nod,const int &par)
{
    c.push_back(vec());
    vec &a=c.back();
    do
    {
        //cout<<"here "<<stk.back()<<' '<<a.back()<<'\n';
        a.push_back(stk.back());
        stk.pop_back();
    }while(a.back()!=nod);
    a.push_back(par);
}

void dfs(int nod, const int &tata)
{
    h[nod]=low[nod]=h[tata]+1;
    //cout<<nod<<','<<h[nod]<<','<<low[nod]<<'\n';
    for(auto e:adj[nod])
    {
        if(e==tata) continue;
        if(h[e]==0)
        {
            stk.push_back(e);
            dfs(e,nod);

            low[nod]=min(low[nod],low[e]);

            if(low[e]>=h[nod]) { addcmp(e,nod);}
        }
        else low[nod]=min(low[nod],h[e]);
    }
}

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<<c.size()<<'\n';
    for(auto v:c)
    {
        for(auto e:v)
        {
            g<<e<<' ';
        }
        g<<'\n';
    }
    return 0;
}