Cod sursa(job #3169522)

Utilizator myrra678ana ana myrra678 Data 15 noiembrie 2023 10:52:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
 #include <fstream>
  
 using namespace std;
  ifstream in("dfs.in");
  ofstream out("dfs.out");
     
int n,m;
 
 
int tata[100001];
int h[100001];
int ffind(int x)
{
  while(tata[x]!=0)
    x=tata[x];
  return x;
} 

void uunion(int r1,int r2)
{
  if(h[r1]<h[r2])
    tata[r1]=r2;
  else if(h[r1]>h[r2])
    tata[r2]=r1;
  else 
  {   tata[r1]=r2;
      h[r2]++;}
  
}

int main() {
  
  int i,x,y;
  in>>n>>m;  
  for(i=1;i<=m;i++)
  {
    in>>x>>y; // muchie
    // lipesc comp conexa a lui + comp conexa a lui y
    int r1=ffind(x);
    int r2=ffind(y);
    if(r1!=r2)
      uunion(r1,r2);
     
  }
  
  
  int cnt=0;
  for(i=1; i<=n; i++)
      if(tata[i]==0)  cnt++;
      
  out<<cnt;
  
  
  return 0;
}