Cod sursa(job #2668096)

Utilizator RomanacheRoman Alexandru-George Romanache Data 4 noiembrie 2020 14:42:58
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>

#define N 200005
#define min(a,b) a<b?a:b

using namespace std;

int n, m, x, y, inceput, i;
int stiva[N], level[N];
vector <int> graf[N];
vector <vector<int> > rasp;

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

void Citire()
{
    f>>n>>m;
    for( i = 0; i < m; i++)
    {
        f>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
}

int Rezolvare(int nod, int tata)
{

    level[nod] = level[tata] + 1;
    stiva[++inceput] = nod;
    int minim = level[nod];
    int l = graf[nod].size();
    for(i = 0; i < l; i++)
    {
        int fiu = graf[nod][i];
        if(fiu == tata)
            continue;
        if(level[fiu])
        {
            minim = min(minim, level[fiu]);
            continue;
        }
        int k = inceput;
        int niv = Rezolvare(fiu, nod);
        if(niv >= level[nod])
        {
            vector <int> comp;
            comp.push_back(nod);
            while(inceput!=k)
            {
                comp.push_back(stiva[inceput]);
                inceput--;
            }
            rasp.push_back(comp);
        }
        minim = min(niv, minim);
    }
    return minim;
}

void Afisare()
{
    int lungime = rasp.size();
    g<<lungime<<"\n";
    for( i = 0; i < lungime; i++)
    {
        int lung2 = rasp[i].size();
        for(int j = 0; j < lung2; j++)
            g<<rasp[i][j]<<" ";
        g<<"\n";
    }
}

int main()
{
    Citire();
    Rezolvare(1,0);
    Afisare();

    return 0;
}