本文共 2207 字,大约阅读时间需要 7 分钟。
(1)
/* 可以通过压缩路径来优化,在查找到祖先节点之后, 将路径上所有它的子孙节点都直接连接到它上面,这样树的高度就大大降低了。*/#includeint num[30005]; //结点所在集合元素的个数int father[30005];void make_set(int x){ 初始化集合 father[x] = -1; num[x] = 1;}int find_set(int x){ 查找x元素所在集合 int r = x, temp; while(father[r] != -1) r = father[r]; //找到根节点 while(x != r){ //压缩路径,将路径上r所有的子孙都直接连接到r上 temp = father[x]; father[x] = r; x = temp; } return x;}void union_(int x, int y){ //合并x, y所在的集合 x = find_set(x), y = find_set(y); if(x == y) return ; //同一个集合则不需要合并 if(num[x] < num[y]) { //小集合合并到大集合 father[x] = y; num[y] += num[x]; } else{ father[y] = x; num[x] += num[y]; }}int main(){ int n, m, t, x, y, i, j; while(scanf("%d %d", &n, &m) && (n || m)){ for(i = 0; i < n; i++) make_set(i); for(i = 0; i < m; i++){ scanf("%d", &t); scanf("%d", &x); for(j = 1; j < t; j++){ scanf("%d", &y); union_(x, y); } } printf("%d\n", num[find_set(0)]); } return 0;}
(2)
/* 对于根节点来说,father[]本身就可以记录节点数目,只不过值是负的。*/#includeint father[30005];void make_set(int x){ //初始化集合 father[x] = -1;}int find_set(int x){ //查找x元素所在集合 int r = x, temp; while(father[r] > 0) r = father[r]; 找到根节点 while(x != r){ //压缩路径,将路径上r所有的子孙都直接连接到r上 temp = father[x]; father[x] = r; x = temp; } return x;}void union_(int x, int y){ //合并x, y所在的集合 x = find_set(x), y = find_set(y); if(x == y) return ; //同一个集合则不需要合并 if(father[x] < father[y]) { 小集合合并到大集合(负数比较), < father[x] += father[y]; father[y] = x; } else{ father[y] += father[x]; father[x] = y; }}int main(){ int n, m, t, x, y, i, j; while(scanf("%d %d", &n, &m) && (n || m)){ for(i = 0; i < n; i++) make_set(i); for(i = 0; i < m; i++){ scanf("%d", &t); scanf("%d", &x); for(j = 1; j < t; j++){ scanf("%d", &y); union_(x, y); } } printf("%d\n", -father[find_set(0)]); //结点数目为负值 } return 0;}
转载地址:http://likxi.baihongyu.com/