Cod sursa(job #3268107)

Utilizator Petru_77Panait Mihai-Petru Petru_77 Data 13 ianuarie 2025 17:30:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 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;
}