题目
源地址:
http://poj.org/problem?id=1611
理解
比较简单的并查集,照着模板敲。
代码
#include <stdio.h>
#include <string.h>
const int N = 30005;
int n, m, f[N], s[N];
int getfar(int x)
{
return x == f[x] ? x : f[x] = getfar(f[x]);
}
void init ()
{
for (int i = 0; i <= n; i++)
{
f[i] = i;
s[i] = 1;
}
int k, a, b;
for (int i = 0; i < m; i++)
{
scanf("%d", &k);
if (k == 0) continue;
scanf("%d", &a);
int p = getfar(a);
for (int j = 1; j < k; j++)
{
scanf("%d", &b);
int q = getfar(b);
if (p != q)
{
f[q] = p;
s[p] += s[q];
}
}
}
}
int main(int argc, char const *argv[])
{
while (scanf("%d%d", &n, &m) == 2 && n + m)
{
init ();
printf("%d\n", s[getfar(0)]);
}
return 0;
}
更新日志
- 2014年08月12日 已AC。