算法笔记之 并查集入门 POJ 1611 (二)

2014-11-24 11:54:39 · 作者: · 浏览: 32
ather
int find_set(int i) {
int temp = i;
while (temp != father[temp]) {
temp = father[temp];
}
father[i] = temp;
return temp;
// if(i != father[i]){
// father[i] = find_set(father[i]); //路径压缩
// }
// return father[i];
}
//合并两个点
void join(int x, int y) {
int i = find_set(x);
int j = find_set(y);
if (i != j) {
father[i] = father[j];
group[j] += group[i]; //合并时,由于最终father保存当前集合人数
}
}

int main() {
int n, m, k;
while (scanf("%d %d", &n, &m) != EOF) {
if (n == 0)
break;
init(n); //初始化
for (int i = 0; i < m; i++) {
scanf("%d", &k);
int pre, cur; //前一个 和 当前
for (int j = 0; j < k; j++) {
scanf("%d", &cur);
if (j) //第一个数不用管
join(pre, cur);
pre = cur;
}
}
//测试
// for(int i=0; i // cout << father[i] << " ";
// cout << endl;
//
// for(int i=0; i // cout << group[i] << " ";
// cout << endl;
//
// cout << find_set(0) << endl;
printf("%d\n", group[find_set(0)]);

}
return 0;
}