Cod sursa(job #1950815)

Utilizator PaulCbnCiobanu Paul PaulCbn Data 3 aprilie 2017 12:03:14
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>

#define NMAX 100005

using namespace std;

int N,M;
vector<int> graf[NMAX];
int viz[NMAX];
int grad[NMAX],sus[NMAX];
void citire()
{
    scanf("%d%d",&N,&M);
    for(int i=1; i<=M; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
}

stack<pair<int,int> > s;
vector<int> rez[NMAX];
int nrComponente;

void elimina_stiva(int primul_nod)
{
    nrComponente++;
    while(s.top().first!=primul_nod)
    {
        rez[nrComponente].push_back(s.top().second);
        s.pop();
    }
    rez[nrComponente].push_back(s.top().second);
    rez[nrComponente].push_back(s.top().first);
    s.pop();
}

void biconex(int nod_curent, int t)
{
    viz[nod_curent]=1;
    sus[nod_curent]=grad[nod_curent]=grad[t]+1;
    for(vector<int>::iterator ii= graf[nod_curent].begin(); ii!=graf[nod_curent].end(); ii++)
    {
        int nod_nou = *ii;
        if(!viz[nod_nou])
        {
            s.push(make_pair(nod_curent,nod_nou));
            biconex(nod_nou,nod_curent);
            sus[nod_curent] = min(sus[nod_curent],sus[nod_nou]);
            if(sus[nod_nou]>=grad[nod_curent])
                elimina_stiva(nod_curent);
        }
        else if(nod_nou!=t)
            sus[nod_curent] = min(sus[nod_curent],grad[nod_nou]);
    }

}

void afisare()
{
    printf("%d\n",nrComponente);
    for(int i=1; i<=nrComponente; i++)
    {
        for(vector<int>::iterator ii = rez[i].begin(); ii!=rez[i].end(); ii++)
            printf("%d ",*ii);
        printf("\n");
    }
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    citire();
    biconex(1,0);
    afisare();
    return 0;
}