Pagini recente » Cod sursa (job #267023) | Cod sursa (job #81833) | Cod sursa (job #596552) | Cod sursa (job #2360400) | Cod sursa (job #3268107)
#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;
}