Cod sursa(job #3268101)

Utilizator StefanPopescu2Popescu Stefan StefanPopescu2 Data 13 ianuarie 2025 17:27:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#define DIM 1000001
  
  
using namespace std;
int tata[DIM],  h[DIM];
 
ifstream fin("dfs.in");
ofstream fout("dfs.out");


int ffind(int x)
{
  int r = x;
  while (tata[r]) r = tata[r];
  while (x != r)
  {
    int y = tata[x];
    tata[x] = r;
    x = y;
  }
  return r;
}
 
void uunion(int r1, int r2)
{
  // r1 != r2
  if(h[r1] > h[r2])
  {
    tata[r2] = r1;
    
  }
  else if(h[r1] < h[r2])
  {
    tata[r1] = r2;
     
  }
  else {
    tata[r1] = r2;
    h[r2]++;
    
  }
} 
  
int main()
{ int n,m; fin>>n>>m; 
  int nrc=n;
  for(int i = 0 ; i < m ; i++)
  {
     int x,y;
      fin >> x >> y ;
      int r1 = ffind(x);
      int r2 = ffind(y);
      if(r1 != r2)
      {
        uunion(r1 , r2 );
        nrc--;
      }
       
     
  }
  fout<<nrc;
   return 0;
}