#include <iostream>
#include <fstream>
#include <cassert>
usingnamespace std;
void main ()
{
ifstream input;
int n,p,q;
int *id,*size;
int counter;
int find (int , int []);
input.open("data-for-union-find.txt",ios::in);
input>>n;
counter=n;
id=newint [n];
assert(id!=0);
size=newint [n];
assert(size!=0);
for (int i=0;i<n;i++)
{
id[i]=i;
}
while (input>>p>>q)
{
int proot, qroot;
proot= find (p,id);
qroot= find (q,id);
if(proot==qroot) return; // Merging
if (size[proot]>size[qroot])
{
id[qroot]==proot;
size[proot]+=size[qroot];
}
else
{
id[proot]=qroot;
size[qroot]+=size[proot];
}
counter--;
}
cout <<counter<<endl;
delete [] id;
delete [] size;
}
int find (int p, int id[])
{
while (id[p]!= p)
p=id[p];
return p;
}
Basically what im trying to do, is open data-for-union-find.txt which ash the following format:
T
X Y
X Y
X Y
X Y
.
.
.
I have to open the file and read from it the 2 sets X and Y and do their union find. The Union find concept is till a bit foggy as i dont fully understand what to do. I get no error while building, but i get no output other then "Press any key to continue ...".
Any thoughts about what to do? As I only really need to know the number of disjoint sets.