初学并查集，我觉得这篇博客通过讲故事的方式，通俗易懂的讲解了并查集，适合初学者看，但是很多问题还有带权、优化等问题，需要具体问题具体分析。
http://blog.csdn.net/dellaserss/article/details/7724401
比如这道3038就是一道带权并查集的问题，题目大意：有n次询问，给出a到b区间的值，问这n次给出的总和中有几次是和前面（先输入的优先级高）已经给出的是矛盾的。
对于这道题来说，加的权，其实就是用sum数组存从i的根（并不一定是1，并有可能被更新）到i的值。需要注意的是，a到b的这个区间，要么是不包括后面这个数，要么是不包括前面这个数，比如说（[1,3],[3,7],如果将这两个数组合并，将会把sum[3]算两遍）这里我们用的是不包括前面的数。 第二个问题，找根Find函数如果用while循环的话，将会超时，而用递归不会，这个..我还不知道为什么。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int pre[200005],sum[200005]; int Find(int x) { if(pre[x] == x) return x; int t = pre[x]; pre[x] = Find(pre[x]); sum[x] += sum[t]; return pre[x]; } int main() { int n,m; while(scanf("%d%d",&n,&m) != EOF) { for(int i=0; i<=n; i++) { pre[i] =i; sum[i] =0; } int ans =0,a,b,c; while(m--) { scanf("%d%d%d",&a,&b,&c); a--; int fa = Find(a); int fb = Find(b); if( fa==fb ) { if( sum[b]-sum[a] != c) ans++; } else { pre[fb] = fa; sum[fb] = sum[a] - sum[b] + c; } } printf("%d\n",ans); } return 0; }