寒假的时候就看到并查集了 当时觉得有点难 另外没怎么听说过这个就没学 这几天想学最小生成树 发现最小生成树等许多东西可以靠并查集来实现 所以今天学习了一下并查集 用我看新算法的老方法 一遍一遍的看 最后终于有了点头绪 跟着教程写了一道题之后 下午自己又独立的做了几道题 感觉还是不错的 当然,有些题没有过 大体的思路我了解 但是可能在一些细节的地方没有处理好 导致wrong 有时间还有继续改
下面是我认为比较合适的并查集模板~ #include < iostream > #include < stdio.h > using namespace std; int father[ 10000001 ],num[ 10000001 ]; /**//* 初始化数组 */ void makeset( int x){ for ( int i = 0 ;i <= x;i ++ ) { father[i] = i; num[i] = 1 ; }} int findset( int x) // 查 { if (x != father[x]) { father[x] = findset(father[x]); } // 回溯 return father[x];} void Union( int a, int b) // 并 { int x = findset(a); int y = findset(b); if (x == y) { return ; } if (num[x] >= num[y]) { father[y] = x; num[x] += num[y]; } else { father[x] = y; num[y] += num[x]; } } int main(){ return 0 ;}转载于:https://www.cnblogs.com/cyiner/archive/2011/05/16/2048225.html
相关资源：JAVA上百实例源码以及开源项目