Cod sursa(job #2121073)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 3 februarie 2018 11:38:57
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
stack <int>s;
vector <int> G[100005];
vector <int> Sol[100005];
struct
{
    int niv,low;
} v[100005];
int m,n,solsize;
void citire()
{
    int aux1,aux2;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&aux1,&aux2);
        G[aux1].push_back(aux2);
        G[aux2].push_back(aux1);
    }
}
void biconex(int nod,int parent)
{
    v[nod].niv=v[parent].niv+1;
    v[nod].low=v[nod].niv;
    s.push(nod);
    for(auto it:G[nod])
    {
        if(it==parent)
            continue;
        if(v[it].niv)
        {
            v[nod].low=min(v[nod].low,v[it].niv);
        }
        else
        {
            biconex(it,nod);
            v[nod].low=min(v[nod].low,v[it].low);
            if(v[it].low>=v[nod].niv)
            {
                Sol[solsize].push_back(nod);
                while(s.top()!=nod)
                {
                    Sol[solsize].push_back(s.top());
                    s.pop();
                }
                solsize++;
            }
        }
    }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    citire();
    biconex(1,0);
    printf("%d\n",solsize);
    for(int i=0; i<solsize; i++)
    {
        for(auto ii:Sol[i])
        {
            printf("%d ",ii);
        }
        printf("\n");
    }
    return 0;
}