Pagini recente » Cod sursa (job #980777) | Monitorul de evaluare | Cod sursa (job #2791001) | Profil tonyX | Cod sursa (job #3314390)
#include <iostream>
#include <fstream>
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
int main(){
int n,m,x,y,nr=0;
fin>>n>>m;
int viz[100001]={0},vecini[100001]={0};
while(m){
fin>>x>>y;
if(viz[x]==0 && viz[y]==0){
nr++;
viz[x]=1;
vecini[x]=nr;
viz[y]=1;
vecini[y]=nr;
}
if(viz[x]==0 && viz[y]!=0){
viz[x]=1;
vecini[x]=vecini[y];
}
if(viz[x]!=0 && viz[y]==0){
viz[y]=1;
vecini[y]=vecini[x];
}
if(viz[x]!=0 && viz[y]!=0 && vecini[x]!=vecini[y])
{
for(int i=1;i<=n;i++){
if(vecini[i]==vecini[y]){
vecini[i]=vecini[x];
}
}
nr--;
}
m--;
}
// for(int i=1;i<=n;i++){
// std::cout<<viz[i]<<" ";
// }
// std::cout<<std::endl;
// for(int i=1;i<=n;i++){
// std::cout<<vecini[i]<<" ";
// }
for(int i=1;i<=n;i++){
if(viz[i]==0){
nr++;
}
}
fout<<nr;
return 0;
}