Cod sursa(job #891885)

Utilizator myshuSpatariu Mihai-Constantin myshu Data 25 februarie 2013 20:57:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>//Spatariu Mihai
using namespace std;//am considerat un arbore care sa memoreze muchiile intre noduri, daca se formeaza ciclu toate nodurile dintr-un subarbore se leaga de radacina
int tata[100001];//vector in care tin minte tatii
void updatetata(int a, int b) //functie ce updateaza vectorul de tati atunci cand se unesc 2 componente conexe
{
    if(tata[b]!=-1)updatetata(a,tata[b]); //atunci cand unesc componentele nodurile din a 2-a componenta conexa se leaga de radacina primei componente
     if(b!=a)tata[b]=a;//radacina are intotdeauna ca tata pe -1 atunci cand are fii si 0 cand e nod izolat
}
int main()
{
    ifstream fcin("dfs.in");
    ofstream fcout("dfs.out");
    int m,i,a,b,n,k=0;
    fcin>>n>>m;
    for(i=1;i<=m;i++)
    {fcin>>a>>b; //citirea unei muchii
     if(tata[a]==0&&tata[b]==0){tata[a]=-1;tata[b]=a;} // cazul in care nodurile a si b sunt noduri izolate
     else if(tata[a]==0){tata[a]=b;} // doar a este nod izolat
     else if(tata[b]==0){tata[b]=a;}// doar b este nod izolat
     else if(tata[a]==-1&&tata[b]==-1){tata[b]=a;} // atat a catsi b sunt radacini... in acest caz e deajuns sa legam doar o radacina ca fiu al celelaltei
     else {while(tata[a]!=-1)a=tata[a];//atunci cand atat a cat si b sunt noduri in 2 componente ce contin minim 2 noduri
            updatetata(a,b);} //updatam vectorul de tati si implicit unim cele 2 componente conexe
     }
     for(i=1;i<=n;i++)
     if(tata[i]==-1||tata[i]==0)k++;// numaram componentele conexe
     fcout<<k<<'\n';
    return 0;
}