| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
并查集。。。。怎么老是wa。。。。。。。#include <stdio.h>
#include <stdlib.h>
int p[30010], rank[30010], m, n;
int find(int x){
if(p[x] != x)
p[x] = find(p[x]);
return p[x];
}
void make(int a, int b){
int min, max;
a = find(a);
b = find(b);
min = a > b ? b : a;
max = a > b ? a : b;
p[max] = min;
}
int cmp(const void* a, const void* b){
return *(int*)a - *(int*)b;
}
int main(){
int i, j, k, a, b;
while(scanf("%d%d", &n, &m), n || m){
for(i = 0; i <= n; i++){
p[i] = i;
}
for(i = 0; i < m; i++){
scanf("%d", &k);
for(j = 0; j < k; j++){
scanf("%d", &a);
if(j)make(b, a);
b = a;
}
}
qsort(p, n, sizeof(p[0]), cmp);n = 0; m = 0;
while(!p[n++])m++;
printf("%d\n", m);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator