Pagini recente » Profil kyrk | Cod sursa (job #1292095) | Diferente pentru concursuri intre reviziile 75 si 74 | Cod sursa (job #713364) | Cod sursa (job #204787)
Cod sursa(job #204787)
//Aflare componenete conexe cu multimi disjuncte
#include<stdio.h>
#define Nmax 100005
int t[Nmax],p[Nmax];
int tata(int k){
while(k!=t[k])
k=t[k];
return k;
}
int main(){
FILE *fin = fopen("dfs.in","r"),
*fout = fopen("dfs.out","w");
int N,M;
fscanf(fin,"%d%d",&N,&M);
for(int i=1;i<=N;i++) t[i]=i,p[i]=1;
for(int i=1;i<=M;i++){
int x,y;
fscanf(fin,"%d%d",&x,&y);
int t1 = tata(x), t2=tata(y);
if(t1!=t2){
if(p[t1] > p[t2])
t[t2]=t1;
else
if(p[t1] < p[t2])
t[t1]=t2;
else{
t[t2]=t1;
p[t1]++;
}
}
}
int cc=0;
for(int i=1;i<=N;i++)
if(t[i]==i)
cc++;
fprintf(fout,"%d\n",cc);
fclose(fin);
fclose(fout);
return 0;
}