Cod sursa(job #852406)

Utilizator dany123Florea Daniel dany123 Data 11 ianuarie 2013 11:09:22
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include<fstream>
#include<cstring>
#include<vector>
#include<stack>

using namespace std;

#define nmax 100001
#define MIN(a,b) a>b?b:a

int N,M,nr_componente;
vector <int> G[nmax],C[nmax]; 
int niv[nmax],niv_min_acc[nmax],tata[nmax]; 
int viz[nmax],aux[nmax]; 
stack<int> stiva;

void adauga_componenta(int nod)
{
    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]);
    }
}

int main()
{
	//citire
    int x,y;
    ifstream fin ("biconex.in");
    fin>>N>>M;
    for(int i=0;i<M;++i)
    {
       fin>>x>>y;
       G[x].push_back(y);
       G[y].push_back(x);
    }
    fin.close();

	//apelare
    for(int i=1;i<=N;++i)
        if(viz[i]==0)
            df(i,1);
    
	//scriere
	ofstream fout("biconex.out");
    fout<<nr_componente<<'\n';
    for(int i=0;i<nr_componente;++i)
    {
        for(vector<int>::iterator it=C[i].begin();it!=C[i].end();++it)
            fout<<*it<<' ';
        fout<<'\n';
    }
    fout.close();

    return 0;
}