Union Find trouble

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <fstream>
#include <cassert>
using namespace 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=new int [n];
assert(id!=0);
size=new int [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.

Thanks in advance
Regards
ifstream is by default set to ios::in so that's not necessary on line 17

what is line 39 returning ?

line 33: change to while(input) or while(input.good())

input>>p>>q goes inside the while loop
Topic archived. No new replies allowed.