nteger
#include<string.h>
#define MAXN 100005
#define MAXM 300005
int N, M;
int father[MAXN];
int findFather(int x) {
if (father[x] == x)
return x;
return father[x] = findFather(father[x]);
}
void unite(int x, int y) {
x = findFather(x);
y = findFather(y);
if (x != y)
father[x] = y;
}
int main() {
while (scanf("%d%d", &N, &M) != EOF) {
for (int i = 0; i <= N; i++)
father[i] = i;
int u, v;
for (int i = 0; i < M; i++) {
scanf("%d%d", &u, &v);
if (findFather(u) != findFather(v))
unite(u, v);
}
int groupCount = 0;
for (int i = 1; i <= N; i++) {
if (findFather(i) == i)
groupCount++;
}
printf("%d\n", groupCount);
}
return 0;
}
```
这是一个典型的并查集(Disjoint Set)问题,出现在ACM(算法竞赛)中。题目描述了有N个人,通过M条消息得知某些人的年龄关系。每条消息表明一个人的年龄不小于另一个人的年龄。目标是将这N个人分成若干组,使得在同一组内的成员之间不存在直接或间接的年龄比较关系,并且每个人必须属于且仅属于一个组。
在并查集中,每个元素都有一个“父亲”节点,代表它所属的集合。初始状态下,每个人都是自己集合的头,即父亲节点是自己。当收到一条消息表明u的年龄不小于v时,如果u和v不属于同一个集合,我们就将u的集合合并到v的集合中,即将u的父节点指向v的父节点。这样,所有年龄关系形成一个树状结构,树的根节点代表一个集合。
在这个问题中,我们需要计算最后有多少个根节点,即有多少个集合,这就是最小的组数。在遍历所有消息后,我们统计有多少个节点的父节点是自身,这个数量就是最终的组数。
参考答案给出的是C++代码实现,主要使用了路径压缩的并查集优化策略。`findFather()`函数用于查找元素的根节点,而`unite()`函数用于合并两个集合。`main()`函数中读取输入,处理每个测试用例,并输出结果。
注意,由于题目限制,数据规模较大,因此在实际编程中要考虑效率较高的数据结构和算法来处理。并查集是一种非常适用于处理这种“连接”和“查询”关系的数据结构,可以有效地解决此类问题。