Cod sursa(job #1833112)

Utilizator calin1Serban Calin calin1 Data 21 decembrie 2016 17:39:53
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <bitset>
#include <stack>
#define N 100005
#define M 200005

using namespace std;

int n, m, nr_articulatii;

vector <int> G[N];

int sus[N], adancime[N];

bitset <N> viz;

stack <int> s;

vector < vector <int> > sol;

void creare_componenta(int nod)
{
    vector <int> tmp;

    tmp.push_back(s.top());

    do
    {
        s.pop();

        tmp.push_back(s.top());
    }
    while(s.top() != nod);

    sol.push_back(tmp);
}

void dfs(int x, int tata)
{
    s.push(x);

    adancime[x] = adancime[tata] + 1;

    sus[x] = adancime[x];

    vector <int> :: iterator it;

    for(it = G[x].begin() ; it != G[x].end() ; ++it)
    {
        if(*it == tata)
        {
            continue;
        }

        if(!viz[*it])
        {
            viz[*it] = true;

            dfs(*it,x);

            sus[x] = min(sus[x],sus[*it]);

            if(adancime[x] <= sus[*it])
            {
                nr_articulatii++;

                creare_componenta(x);
            }
        }
        else
        {
            sus[x] = min(sus[x],adancime[*it]);
        }
    }
}

void afisare()
{
    for(int i = 0 ; i < sol.size() ; ++i)
    {
        for(int j = 0 ; j < sol[i].size() ; ++j)
        {
            printf("%d ",sol[i][j]);
        }
        printf("\n");
    }
}

void citire()
{
    scanf("%d %d\n",&n,&m);

    int x, y;

    for(int i = 0 ; i < m ; ++i)
    {
        scanf("%d %d\n",&x,&y);

        G[x].push_back(y);
        G[y].push_back(x);
    }

    adancime[0] = -1;

    for(int i = 1 ; i <= n ; ++i)
    {
        if(!viz[i])
        {
            viz[i] = true;

            dfs(i,0);
        }
    }

    printf("%d\n",nr_articulatii);

    afisare();
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);

    citire();

    return 0;
}