Cod sursa(job #849613)

Utilizator StefanLacheStefan Lache StefanLache Data 7 ianuarie 2013 13:23:41
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.52 kb
#include<stdio.h>
#include<cstring>
#include<vector>
#include<stack>
#define nmax 100001
#define MIN(a,b) a>b?b:a
using namespace std;
int N,M,nr_componente;
vector <int> G[nmax],C[nmax];                            //G pentru listele de adiacenta,C pentru componente;
int niv[nmax],niv_min_acc[nmax],tata[nmax];         ///niv nivelul nodului,niv_min_acc nivelul minim accesibil,tata vectorul de tati;
int viz[nmax],aux[nmax];                                    //viz vectorul de vizitare,aux pentru componentele biconexe;
stack<int> stiva;
void citeste()
{
    int i,x,y;
    FILE *f=fopen("biconex.in","rt");
    fscanf(f,"%i%i",&N,&M);
    for(i=0;i<M;++i)
    {
        fscanf(f,"%i%i",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    fclose(f);
}
void adauga_componenta(int nod)
{
    memset(aux,0,sizeof(aux));
    int x;
    while(stiva.top() != nod)
    {
        x=stiva.top();
        if(aux[x]==0)
            C[nr_componente].push_back(x);
        aux[x]=1;
        stiva.pop();
    }
    if(aux[stiva.top()]==0)
        C[nr_componente].push_back(stiva.top());
    ++nr_componente;
}
void df(int nod,int nivel)
{
    viz[nod]=1;
    niv_min_acc[nod]=nivel;
    niv[nod]=nivel;
    stiva.push(nod);
    for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();++it)
    {
        int x=*it;
        if(viz[x]==0)
        {
            stiva.push(nod);                //adaugam in stiva;
            tata[x]=nod;                //actualizam vectorul de tati;
            df(x,nivel + 1);               //facem o parcurgere si din nodul fiu x;
            niv_min_acc[nod]=MIN(niv_min_acc[nod],niv_min_acc[x]);              //nivelul minim accesibil este minimul dintre nivelul minim accesibil al sau si al tuturor fiilor
            if(niv_min_acc[x]>=niv[nod])                    //atunci   "nod" este nod critic   si va incepe o noua componenta biconexa
                adauga_componenta(nod);
        }
        else if(tata[nod]!=x)          //muchie de intoarcere
            niv_min_acc[nod]=MIN(niv[x],niv_min_acc[nod]);
    }
}
void afiseaza()
{
    FILE *g=fopen("biconex.out","wt");
    fprintf(g,"%i\n",nr_componente);
    for(int i=0;i<nr_componente;++i)
    {
        for(vector<int>::iterator it=C[i].begin();it!=C[i].end();++it)
            fprintf(g,"%i ",*it);
        fprintf(g,"\n");
    }
    fclose(g);
}
int main()
{
    citeste();
    int i;
    for(i=1;i<=N;++i)
        if(viz[i]==0)
            df(i,1);
    afiseaza();
    return 0;
}