并查集
并查集故名思义,就是一个集合既能够合并,也能够查找。因此通常有两个函数,find和merge。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
class { int size; int[] pre; public (int size) { this.size = size; pre = new int[size]; for(int i = 0; i < size; i++) { pre[i] = i; } } public int find(int x) { int r = x; while(pre[r] != r) r = pre[r]; return r; } public void merge(int x, int y) { int fx = find(x), fy = find(y); if(pre[fx] != pre[fy]) { pre[fx] = fy; } } }
|
近期评论