기본 구현

#include 
#include 
#include 

#define FOR(n) for( int i = 0 ; i < n ; i ++ )
using namespace std;

//      
class UnionFind{

private:
	int* id;
	int count;
public:
	UnionFind( int n ){
		id = new int[n];
		this->count = n;
		for( int i = 0 ; i < n ; i ++ )
			id[i] = i;
	}
	~UnionFind(){
		delete[] id;
	}
	//  p  
	int find( int p ){
		assert( p >= 0 && p < count );
		return id[p];
	}
	//  p q     
	bool isConnected( int p , int q ){
		return find(p) == find(q);
	}
	// q q    
	void unionElements( int p , int q ){
		int qID = find(q);
		int pID = find(p);
		if( pID == qID )
			return;

		for( int i = 0 ; i < count ; i ++ ){
			if( id[i] == qID )
				id[i] = pID;
		}
	}

	void println(){
		FOR(count)
			cout << id[i] << endl;
	}
};

#include 
#include 
#include 

#define FOR(n) for( int i = 0 ; i < n ; i ++ )
using namespace std;

//          
class UnionFind2{

private:
	int* parent;
	int count;

public:
	UnionFind2( int n ){
		parent = new int[n];
		this->count = n;
		FOR(n)
			parent[i] = i;		
	}
	~UnionFind2(){
		delete[] parent;
	}
	// p    
	int find( int p ){
		assert( p >= 0 && p < count );
		// parent[p] = p                 "   " p  
		while( parent[p] != p )
			p = parent[p];
		return p;
	}
	bool isConnected( int p , int q ){
		//          
		return find(p) == find(q);
	}
	void unionElements( int p , int q ){
		int Rootp = find(p);
		int Rootq = find(q);

		if( Rootp == Rootq )
			return;
		//          Rootp     Rootq           
		parent[Rootp] = Rootq;
	}
	void println(){
		FOR(count)
			cout << i << " ";
		cout << endl;

		FOR(count)
			cout << parent[i] << " ";
		cout << endl;
	}
};

#include 
#include 
#include 

#define FOR(n) for( int i = 0 ; i < n ; i ++ )
using namespace std;

/************************************************************************/
/*									size                                                                       */
/************************************************************************/
class UnionFind3{

private:
	int* parent;
	int* sz;
	int count;

public:
	UnionFind3( int n ){
		parent = new int[n];
		sz = new int[n];
		this->count = n;
		FOR(n){
			parent[i] = i;
			sz[i] = 1;
		}	
	}
	~UnionFind3(){
		delete[] sz;
		delete[] parent;
	}
	// p    
	int find( int p ){
		assert( p >= 0 && p < count );
		// parent[p] = p                 "   " p  
		while( parent[p] != p )
			p = parent[p];
		return p;
	}
	bool isConnected( int p , int q ){
		//          
		return find(p) == find(q);
	}
	void unionElements( int p , int q ){
		int Rootp = find(p);
		int Rootq = find(q);

		if( Rootp == Rootq )
			return;
		//          Rootp     Rootq           
		//parent[Rootp] = Rootq;
		if( sz[Rootp] < sz[Rootq] ){
			parent[Rootp] = Rootq;
			sz[Rootq] += sz[Rootp];
		}
		else{
			parent[Rootq] = Rootp;
			sz[Rootp] += sz[Rootq];
		}
	}
	void println(){
		FOR(count)
			cout << i << " ";
		cout << endl;

		/*	FOR(count)
		cout << parent[i] << " ";
		cout << endl;*/
		FOR(count){
			cout << i << "->" << parent[i] << endl;
		}
	}
};

#include 
#include 
#include 

#define FOR(n) for( int i = 0 ; i < n ; i ++ )
using namespace std;

// rank  
/************************************************************************/
/*						                                                                           */
/************************************************************************/
class UnionFind4{

private:
	int* parent;
	int* rank;
	int count;

public:
	UnionFind4( int n ){
		parent = new int[n];
		rank = new int[n];
		this->count = n;
		FOR(n){
			parent[i] = i;
			rank[i] = 1;
		}

	}
	~UnionFind4(){
		delete[] rank;
		delete[] parent;
	}
	// p    
	int find( int p ){
		assert( p >= 0 && p < count );
		// parent[p] = p                 "   " p  
		//while( parent[p] != p ){
		//	parent[p] = parent[parent[p]];
		//	p = parent[p];
		//}
		//return p;
		if( p != parent[p] )
			parent[p] = find(parent[p]);
		
		return parent[p];
	}
	bool isConnected( int p , int q ){
		//          
		return find(p) == find(q);
	}
	void unionElements( int p , int q ){
		int Rootp = find(p);
		int Rootq = find(q);

		if( Rootp == Rootq )
			return;
		//          Rootp     Rootq           
		//parent[Rootp] = Rootq;
		if( rank[Rootp] < rank[Rootq] )
			parent[Rootp] = Rootq;
		
		else if( rank[Rootq] < rank[Rootp] )
			parent[Rootq] =  Rootp;
		//rank[Rootq] == rank[Rootp]
		else {
			parent[Rootp] = Rootq;
			rank[Rootq] += 1;
		}
			
		
	}
	void println(){
		FOR(count)
			cout << i << " ";
		cout << endl;

		FOR(count)
			cout << parent[i] << " ";
		cout << endl;
	}
};

#include 
#include 
#include 
#include "UnionFind1.h"
#include "UnionFind2.h"
#include "UnionFind3.h"
#include "UnionFind4.h"
#define FOR(n) for( int i = 0 ; i < n ; i ++ )

using namespace std;



void test1( int n ){

	UnionFind uf(n);
	time_t start = clock();

	for( int i = 0 ; i < n ; i ++ ){
		int a = rand()%n;
		int b = rand()%n;
		uf.unionElements(a,b);
	}

	for( int i = 0 ; i < n ; i ++ ){
		int a = rand()%n;
		int b = rand()%n;
		uf.isConnected(a,b);
	}
	time_t end = clock();
	cout << "Times:" << double(end-start)/CLOCKS_PER_SEC << "s" <