Pagini recente » Cod sursa (job #1746541) | Cod sursa (job #2100124) | Cod sursa (job #2899049) | Cod sursa (job #1401728) | Cod sursa (job #891885)
Cod sursa(job #891885)
#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;
}