Cod sursa(job #1096566)

Utilizator andreea_alexandraAndreea Alexandra andreea_alexandra Data 2 februarie 2014 12:28:12
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
int const MAX_N=100001, MAX_M=200001;
int N, M, nivel[MAX_N], k, niv_min;
vector<int> G[MAX_N];
vector<pair <int, int> > st;
set<int> BC[MAX_M];
bool vizitat[MAX_N];

void citeste()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for(int i=0; i<M; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void ScrieComp(int o, int d)
{
    pair<int, int> muchie;
    k++;
    do
    {
        int x, y;
        muchie=st.back();
        x=muchie.first;
        y=muchie.second;
        BC[k].insert(muchie.first);
        BC[k].insert(muchie.second);
        st.pop_back();
    }
    while(muchie.first!=o || muchie.second!=d);
}

void ComponenteBiconexe(int nod, int parinte, int niv)
{
    if(vizitat[nod])
        niv_min=nivel[nod];
    else
    {
        vizitat[nod]=true;
        nivel[nod]=niv;
        niv_min=niv;
        for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++)
        {
            if(!vizitat[*it])
            {
                st.push_back(make_pair(nod, *it));
                ComponenteBiconexe(*it, nod, niv+1);
                if(niv<=nivel[*it])
                    ScrieComp(nod, *it);
            }
            if(*it!=parinte)
                nivel[nod]=min(nivel[*it], nivel[nod]);

        }
    }
}
int main()
{
    citeste();
    ComponenteBiconexe(1, 0, 0);
    printf("%d\n", k);
    for(int i=1; i<=k; i++)
        {for(set<int>::iterator it=BC[i].begin(); it!=BC[i].end(); it++)
            printf("%d ", *it);
         printf("\n");
        }
    return 0;
}