Cod sursa(job #2669058)

Utilizator jucatorulGrigore George Alexandru jucatorul Data 5 noiembrie 2020 23:10:13
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define N 100001
#define pb push_back
using namespace std;



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

int m,x,y;

int n,nivel[N],nma[N],viziat[N],stiva[N],counter,nr;
vector <int> vecin[N],Componente[N];

void dfs(int nod, int parinte)
{
    viziat[nod]=1;
    nma[nod]=nivel[nod];
    stiva[++counter]=nod;
    for(auto i : vecin[nod])
    {
        if(i==parinte)continue;
        if(viziat[i])
            nma[nod]=min(nma[nod],nivel[i]);
        else
        {
            nivel[i]=nivel[nod]+1;

            dfs(i,nod);



            if(nma[i]>=nivel[nod])
            {
                ++nr;
                while(counter && stiva[counter]!=i)
                    Componente[nr].pb(stiva[counter--]);
                Componente[nr].pb(stiva[counter--]);
                Componente[nr].pb(nod);
            }
            nma[nod]=min(nma[nod],nma[i]);
        }
    }
}

int main()
{

    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y;
        vecin[x].pb(y);
        vecin[y].pb(x);
    }
    dfs(1,0);
    g<<nr<<endl;
    for(int i=1; i<=nr; ++i)
    {
        for(auto j : Componente[i]) g<<j<<" ";
        g<<endl;
    }
    return 0;
}