并查集总结

并查集详解：http://blog.csdn.net/dellaserss/article/details/7724401

模板：

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

//并查集
struct DisjointSet {
	std::vector<int> father, rank;		//元素的父亲节点，树根元素所代表集合的rank
	//初始化
	DisjointSet(int n) : father(n), rank(n) {
		for (int i = 0; i < n; ++i)
			father[i] = i;
	}
	//查找v所在集合的代表元
	int find(int v) {
		return father[v] = father[v] == v ? v : find(father[v]);
	}
	/*非递归 
	int find(int v) {
	int p, tmp;
	p = v;
	while (v != father[v])
		v = father[v];
	while (p != v) {
		tmp = father[p];
		father[p] = v;
		p = tmp;
	}
	return v;
	}*/
	//合并x所在集合与y所在集合
	void merge(int x, int y) {
		int a = find(x), b= find(y);
		if (rank[a] < rank[b])
			father[a] = b;
		else {
			father[b] = a;
			if (rank[a] == rank[b])
				++rank[a];
		}
	}
};

例题：fjutoj2144 

很直白的并查集，维护一下num、Max、setnum即可，实测find递归形式不会爆栈

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

//并查集
struct DisjointSet {
	int setnum;
	std::vector<int> father, rank, num, Max;		//元素的父亲节点，树根元素所代表集合的rank
	//初始化
	DisjointSet(int n) : father(n + 1), rank(n + 1), num(n + 1), Max(n + 1) {
		setnum = n;
		for (int i = 1; i <= n; ++i) {
			father[i] = i;
			num[i] = 1;
			Max[i] = i;
		}
	}
	//查找v所在集合的代表元
	/*
	int find(int v) {
		int p, tmp;
		p = v;
		while (v != father[v])
			v = father[v];
		while (p != v) {
			tmp = father[p];
			father[p] = v;
			p = tmp;
		}
		return v;
	}*/
	int find(int v) {
		return father[v] = father[v] == v ? v : find(father[v]);
	}
	//合并x所在集合与y所在集合
	void merge(int x, int y) {
		int a = find(x), b= find(y);
		if (a != b) {
			if (rank[a] < rank[b]) {
				father[a] = b;
				Max[b] = max(Max[a], Max[b]);
				num[b] += num[a];
			} else {
				father[b] = a;
				Max[a] = max(Max[a], Max[b]);
				num[a] += num[b];
				if (rank[a] == rank[b])
					++rank[a];
			}
			--setnum;
		}
	}
};

int main()
{
	int n, m, x, y;
	while (~scanf("%d%d", &n, &m)) {
		DisjointSet s = DisjointSet(n);
		char op[10];
		while (m--) {
			scanf("%s", op);
			if (op[0] == 'u') {
				scanf("%d%d", &x, &y);
				s.merge(s.find(x), s.find(y));
			} else if (op[0] == 's' && op[1] == 'a') {
				scanf("%d%d", &x, &y);
				if (s.find(x) == s.find(y))
					printf("1\n");
				else
					printf("0\n");
			} else if (op[0] == 'n') {
				scanf("%d", &x);
				printf("%d\n", s.num[s.find(x)]);
			} else if (op[0] == 'm') {
				scanf("%d", &x);
				printf("%d\n", s.Max[s.find(x)]);
			} else
				printf("%d\n", s.setnum);
		}
	}
	return 0;
}