Cod sursa(job #836624)

Utilizator cdascaluDascalu Cristian cdascalu Data 16 decembrie 2012 13:50:41
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include<stdio.h>
#include<vector>
#include<stack>
#include<bitset>
#define Nmax 100001
using namespace std;

vector<int> G[Nmax],C[Nmax];
int niv[Nmax],l[Nmax],T[Nmax];//niv[i] = nivelul nodului; l[i] cel mai  de sus nod(jos ca nivel) unde poate ajunge
int N,M,nr_c;
bitset<Nmax> viz,aux;
stack< int > S;
void read_data()
{
    FILE*f = fopen("biconex.in","r");
    fscanf(f,"%d%d",&N,&M);
    int x,y;
    while(M--)
    {
        fscanf(f,"%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    fclose(f);
}
int minim(int a,int b)
{
    if(a<=b)
        return a;
    return b;
}
void get_comp(int nod)
{
    aux.reset();
    int x;
    while(S.top() != nod)
    {
        x = S.top();
        if(aux[x] == false)
            C[nr_c].push_back(x);

        aux[x] = true;
        S.pop();
    }
    if(aux[S.top()] == false)
        C[nr_c].push_back(S.top());
    ++nr_c;
}
void df(int nod,int nivel)
{
    niv[nod]         = nivel;
    l[nod]           = nivel;
    viz[nod]         = true;
    S.push(nod);
    int x;
    for(vector<int>::iterator it = G[nod].begin();it!=G[nod].end();++it)
    {
        x = *it;
        if(viz[x] == false)
        {
            S.push(nod);//adaug in stiva 1-2 2-3 3-4...

            T[x] = nod;
            df(x,nivel+1);
            l[nod] = minim(l[x], l[nod]);//obtin minimul posibil(cu toate muchiile de intoarcere din fii)

            if(l[x] >= niv[nod])//nod = T[x]
                get_comp(nod);
        }
        else if(T[nod] != x)//inseamna ca am o muchie de intoarcere
            l[nod] = minim(niv[x], l[nod]);
    }
}
int main()
{
    read_data();

    for(int i=1;i<=N;++i)
    {
        if(viz[i] == false)
            df(i,1);
    }

    FILE*g = fopen("biconex.out","w");
    fprintf(g,"%d\n",nr_c);

    for(int i=0;i<nr_c;++i)
    {
        for(vector<int>::iterator it = C[i].begin();it!=C[i].end();++it)
        {
            fprintf(g,"%d ",*it);
        }
        fprintf(g,"\n");
    }
    fclose(g);
    return 0;
}