首页 > 学院 > 开发设计 > 正文

poj 1611 The Suspects(并查集)

2019-11-11 02:55:12
字体:
来源:转载
供稿:网友

include

int f[30010]; int n,m;

int getf(int x) { if(x == f[x]) return x; return (f[x] = getf(f[x])); }

void merge(int a, int b) { a = getf(a); b = getf(b); if(a != b) { if(b == 0) f[a] = b; else if(a == 0) f[b] = a; else f[b] = a; } }

int main() { int a,b,k,res; while(scanf(“%d %d”,&n,&m) && n) { res = 0; for(int i = 0; i < n; ++i) f[i] = i; for(int i = 0; i < m; ++i) { scanf(“%d %d”,&k,&a); for(int j = 1; j < k; ++j) { scanf(“%d”,&b); merge(a,b); } } //本来以为这样会超时呢,没想到才16M for(int i = 0; i < n; ++i) if(getf(i) == 0) ++res; PRintf(“%d/n”,res); } return 0; }


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表