题目链接:1611 -- The Suspects (poj.org)

题目大意(我自己翻的):
SARS病毒很猛,接触了就感染,0号是最初的感染者,接下来将编号为0~n-1的人分组(同一个组内的人都发生了接触),问有多少人会感染SARS?
输入格式(多组输入)
n m
k1 a1 a2 a3...ak1
k2 a1 a2 a3...ak2
km a1 a2 a3...akm
当n m都为0时结束。
思路
这是一道简单的并查集模板题,最后输出和0相连的点的数量即可。
如果不懂并查集请看这篇文章https://www.eriktse.com/algorithm/51.html
代码
/* Copyright (C) 2022 ErikTse */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <bitset>
#include <queue>
#include <utility>
#include <stack>
#include <algorithm>
#define pb push_back
#define fi first
#define se second
#define pr printf
#define sc scanf
#define gc getchar
#define int long long
//请使用%lld输出long long类型数据
using namespace std;
inline int re(){
int s = 0,w = 1;char c = gc();
while(c > '9' || c < '0'){if(c == '-')w = -1;c = gc();}
while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
return s * w;
}
/*-------全局变量------*/
const int maxn = 1e5 + 10;
int N, M;
int pre[maxn];
/*------自定义函数-----*/
inline int root(int x)
{
int rx = x;
while(pre[rx] != rx)rx = pre[rx];
return pre[x] = rx;//此时rx为x的根,将x直接指向根,进行路径压缩并返回根
}
inline void init(){for(int i = 0;i < N; ++ i)pre[i] = i;}//注意本题节点编号是0 ~ N - 1
inline void Merge(int x,int y){pre[root(x)] = root(y);}
inline bool iscon(int x,int y){return root(x) == root(y);}
signed main()
{
//freopen("in.txt","r",stdin);
while(cin >> N >> M && (N != 0 || M != 0))
{
init();
while(M --)//进行 M 次分组
{
int k = re();//re()是快速读入,每组 k 个人
int last = 0;//表示上一个点
for(int i = 1, tmp;i <= k; ++ i)
{
tmp = re();//tmp为当前点
if(i > 1)Merge(tmp, last);
last = tmp;
}
}
//合并完成
int ans = 0;//ans应该是所有和 0 连通的点
for(int i = 0;i < N; ++ i)if(iscon(0, i))ans ++;
pr("%lld\n",ans);//int类型宏定义成了long long
}
return 0;
}
希望对你有帮助。
Comments NOTHING