Pagini recente » Cod sursa (job #1913179) | Cod sursa (job #1950681) | Cod sursa (job #1365000) | Cod sursa (job #333267) | Cod sursa (job #891992)
Cod sursa(job #891992)
#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 n,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
else if(b!=a)n--; //daca unim 2 elemente conexe care nu au nici un stramos comun scadem nr total de elemente conexe
if(b!=a)tata[b]=a;//radacina are intotdeauna ca tata pe -1 atunci cand are fii si 0 cand e nod izolat
}
int updatea(int a)//legam fiecare tata a lui a de radacina pentru a lucra mai usor ulterior si pt a evita parcurgeri repetate pe multe elemente
{
if(tata[a]==-1) return a;
tata[a]=updatea(tata[a]);
return tata[a];
}
int main()
{
ifstream fcin("dfs.in");
ofstream fcout("dfs.out");
int m,i,a,b,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;n--;} // cazul in care nodurile a si b sunt noduri izolate
else if(tata[a]==0){tata[a]=b;n--;} // doar a este nod izolat
else if(tata[b]==0){tata[b]=a;n--;}// doar b este nod izolat
else if(tata[a]==-1&&tata[b]==-1){tata[b]=a;n--;} // atat a catsi b sunt radacini... in acest caz e deajuns sa legam doar o radacina ca fiu al celelaltei
else {a=updatea(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
}
fcout<<n<<'\n';// am avut grija sa scadem n atunci cand uneam 2 componente conexe astfel, ce ramane vor fi nr de componente conexe ramase
return 0;
}