Cod sursa(job #1832681)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 20 decembrie 2016 18:44:06
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

int n, m, nivelActual[100005], nivelSus[100005], viz[100005], numarComponente=0;
vector <int> g[100005];
vector <vector <int> > vect;
stack <int> s;

void read()
{
    scanf("%d%d", &n, &m);
    int x, y;
    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void adaugareComponente(int x, int nod)
{
    vector <int>::iterator it;
    vector <int> aux;
    aux.push_back(nod);
    while(s.top()!=x)
    {
        aux.push_back(s.top());
        s.pop();
    }
    aux.push_back(x);
    s.pop();
    vect.push_back(aux);
}

void dfs(int x, int tata)
{
    vector <int>::iterator it;
    viz[x]=1;
    nivelActual[x]=nivelActual[tata]+1;
    nivelSus[x]=nivelActual[x];
    for(it=g[x].begin(); it!=g[x].end(); ++it)
    {
        if(*it==tata)
            continue;

        if(viz[*it]==0)
        {
            s.push(*it);
            dfs(*it, x);
            if(nivelSus[*it]<nivelSus[x])
                nivelSus[x]=nivelSus[*it];
            if(nivelSus[*it]>=nivelActual[x])
                {
                    numarComponente++;
                    adaugareComponente(*it, x);
                }
        }
        else
        {
            if(nivelSus[*it]<nivelSus[x])
                nivelSus[x]=nivelSus[*it];
        }
    }
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    read();
    nivelActual[0]=-1;
    for(int i=1; i<=n; ++i)
        if(viz[i]==0)
            dfs(i, 0);
    printf("%d\n", numarComponente);
    vector <vector <int> >::iterator itvect;
    vector <int>::iterator it;
    for(itvect=vect.begin(); itvect!=vect.end(); ++itvect)
    {
        for(it=itvect->begin(); it!=itvect->end(); ++it)
            printf("%d ", *it);
        printf("\n");
    }
    return 0;
}