Cod sursa(job #2669029)

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



ifstream fin("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;
    nivel[nod]=nivel[parinte]+1;
    nma[nod]=nivel[nod];
    stiva[++counter]=nod;
    for(auto i : vecin[nod])
    {
        if(i!=parinte)
        if(viziat[i])
            nma[nod]=min(nma[nod],nivel[i]);
        else
        {

            dfs(i,nod);

                nma[nod]=min(nma[nod],nma[i]);

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

        }
    }
}

int main()
{

    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>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;
}