【并查集】poj1611 – The Suspects

发布于 2022-02-24  782 次阅读


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

poj1611题目描述

题目大意(我自己翻的):

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;
}

希望对你有帮助。

19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09