The Suspects 并查集(模板)

54 阅读 0 评论 36 点赞

我是靠谱客的博主唠叨康乃馨，最近开发中收集的这篇文章主要介绍The Suspects 并查集(模板)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

并查集

并查集简单来说就是一个寻找头目的过程,比如寻找病毒源头,公司老大,幕后黑手
核心代码

int f[10005];//记录结点的上一级 
void inti(int x)//初始化结点上一级是本身 
{
	for(int i=0;i<x;i++)
	{
		f[i]=i;
	} 
} 
int fdroot(int x)//寻找源头函数
{
	if(f[x]==x)
		return x;
	else
		return f[x]=fdroot(f[x]);//如果这个x上头有人,就递归再往上找
}
void join(int x,int y)//合并集团,比如题目是什么一个人掌管多个部门了,多职位那种,管多人就需要将两个集合合并
{
	int rx=fdroot(x);
	int ry=fdroot(y);
	if(rx!=ry)//如果不是两个集合
	{
		f[rx]=ry;//直接将x的上级并到y的上级上
	}
}

题目练习

The Suspects

题目链接
题目大概意思就是现在有n个人,m个小团体,里面有个标号为0的同学疑似感染了病毒需要隔离他和他接触过的人,然后每组数据第一行输入n和m,接下来每一行输入小团体人数,以及他们的编号0 < n <= 30000 and 0 <= m <= 500.

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<map>
#include<set> 
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<math.h> 
using namespace std;
typedef long long int ll; 
int f[50010];//记录结点的源头
int ans[50010];//记录感染编号 
void inti(int x)//初始化结点源头是本身 
{
	for(int i=0;i<x;i++)
	{
		f[i]=i;
	} 
} 
int fdroot(int x)
{
	if(f[x]==x)
		return x;
	else
		return f[x]=fdroot(f[x]);
}
void join(int x,int y)
{
	int rx=fdroot(x);
	int ry=fdroot(y);
	if(rx!=ry)
	{
		f[rx]=ry;
	}
}
int main()
{
	int n,m;//n为总人数,m为几个团体
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n==0&&m==0)
			break;
		inti(n);
		int rs;
		for(int i=0;i<m;i++)
		{
			scanf("%d",&rs);
			int jd1,jd2;//结点1,结点2
			scanf("%d",&jd1);
			for(int j=1;j<rs;j++)
			{
				scanf("%d",&jd2);
				join(jd1,jd2);
			}
		}
		int by=fdroot(0);//病原为标号0
		int cnt=0;
		for(int i=0;i<n;i++)
		{
			if(fdroot(i)==by)
			{
				ans[cnt++]=i;
			}
		}
		printf("%dn",cnt);//根据题目要求输出，还可以输出ans中的隔离编号
	} 
	return 0;
}