首页 > 其他分享 >信息传递(题解)[并查集]

信息传递(题解)[并查集]

时间:2024-03-02 15:00:22浏览次数:22  
标签:同学 游戏 int 题解 查集 信息 传递 Ti

题目

题目描述

有n个同学(编号为1到n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为i的同学的信息传递对象是编号为Ti同学。
游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?

输入格式

输入共2行。
第1行包含1个正整数n表示n个人。
第2行包含n个用空格隔开的正整数T1,T2,……,Tn其中第i个整数Ti示编号为i的同学的信息传递对象是编号为Ti的同学,Ti≤n且Ti≠i
数据保证游戏一定会结束。

输出格式

输出共 1 行,包含 1 个整数,表示游戏一共可以进行多少轮。

样例

样例输入

5
2 4 2 3 1

样例输出

3

我的思路

题目要求在一个同学听到自己的生日后停止,他自己的生日显然只能由自己传出,所以可以在每次更新一个同学的根节点时,只进行更新,而不进行压缩,让构造的图像最终可以形成一个环,当形成环时,游戏结束。下面给代码。

代码

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;

int n,ans;
int fa[maxn],information[maxn];

int getfa(int x)
{
	ans++;
	if(x==fa[x])return x;
	return getfa(fa[x]);//只查询不压缩
}

void merge(int x,int y)
{
	fa[y]=x;//传递信息没有条件
}

int main()
{
	cin >>n;
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	int cnt=0x3f3f3f3f;
	for(int i=1;i<=n;i++)//分别求每个同学结束游戏需要的轮数
	{
		int x;
		cin >>x;
		ans=0;
		int fx=getfa(x);
		if(fx==i)
		{
			cnt=min(cnt,ans);//求最短游戏轮数
		}
		else
		{
			merge(x,i);
		}
	}
	cout <<cnt;
	
	return 0;
}

标签:同学,游戏,int,题解,查集,信息,传递,Ti
From: https://www.cnblogs.com/wang-qa/p/18048644

相关文章

  • P10187 [USACO24FEB] Palindrome Game B 题解
    挑战题解区最短代码回文数?数学题!打表找规律吧……显然,\(1\sim9\)都是回文数,先手赢(就一位你还想咋地啊)。然后是\(10\)。样例告诉我们,这个不行。接着是\(11\sim19\),发现随便减个\(1\sim9\)就可以变成\(10\),而\(10\)是后手赢。赢得就是后手的后手,那就是先手,可以。......
  • P10189 [USACO24FEB] Maximizing Productivity B 题解
    先说说暴力做法:每次遍历一遍,看看是否满足\(t_i+s\lec_i\),满足就计数,不满足就挂。单次时间复杂度显然为\(O(N)\),总得时间复杂度约为\(O(NQ)\),TLE是肯定的~暴力代码//Problem:Problem3.MaximizingProductivity//Contest:USACO-USACO2024FebruaryContest,......
  • ABC295D 题解
    萌萌思维题,但是考场差一点AC。题目等价于寻找区间\([l,r]\)满足数字\(0\)~\(9\)各出现偶数次。根据找筷子这道题的经验,出现偶数次=异或和为\(0\)。但是发现如果和找筷子一样直接异或到一起会出现冲突(例子:$3\oplus5\oplus6=0$)。所以变成二进制数就可以了。......
  • ABC321F 题解
    可撤销背包的模板题。如果没有减操作就是\(01\)背包,众所周知转移方程是\(f[i]=f[i]+f[i-v]\)。考虑减操作,对于一个重量\(i\),不选物品\(v\)的方案数是什么呢?发现我们只需要把选\(v\)的方案去掉就好,那么转移方程就是\(f[i]=f[i]-f[i-v]\)。于是就做完了。注意取模变正......
  • ABC323D 题解
    这个题笔者场上Wa了六次……首先发现一个性质:考虑单个的\(s\),它自己所能合并成的块就是\(c\)的二进制表示。例如当\(s=3,c=7\)时,显然我们可以先两两合并,得到\(3\)个\(s=6\)的,再把其中的两个合并得到一个\(s=12\)的。发现\(7=(111)_2\),正好最终只有三个块:\(s=3,......
  • P3749 题解
    P3749[六省联考2017]寿司餐厅题解发现很少有人讲为什么这题是最大权闭合子图,但作为一个刚学网络流的蒟蒻,我认为考虑是必要的。最大权闭合子图的特点:存在单向依赖关系,选\(x\)必须选\(y\)。每个点只会被选一次。代价有正有负。本问题特点:选一个区间,必选所有子区间(......
  • ABC338G 题解
    ABC338G题解计数题,没有太多思维难度,就是麻烦。显然+和*是比较难搞的,应考虑子问题。复杂度要求线性,考虑每个位置的贡献。Case1:只有数字Ex:1234考虑2的贡献,枚举一下看看。\(12=1\times10+2\times1\)\(123=1\times100+2\times10+3\times1\)\(1234=\dots\)\(2=2......
  • 并查集(模板介绍+路径压缩)
    并查集(模板介绍+路径压缩)题面P3367并查集题目描述如题,现在有一个并查集,你需要完成合并和查询操作。第一行包含两个整数N,M,表示共有N个元素和M个操作。接下来M行,每行包含三个整数Z,X,Y。当Z=1时,将X与Y所在的集合合并。当Z=2时,输出Z与Y是否在同一集合内,是的输出Y;否则输出N......
  • [ABC217F] Make Pair 题解
    [ABC217F]MakePair题解思路解析通过\(n\le200\)和“选出的两个学生离开队列,空出来的位置左右合拢”这两个细节可以想到能用区间dp做,\(f_{i,j}\)表示将\(i\toj\)这个区间全部选完的方案数,然后常规区间dp,加一个判断如果当前区间\([l,r]\)中\(l,r\)是朋友,就可......
  • P4690 [Ynoi2016] 镜中的昆虫 题解
    题目链接:镜中的昆虫经典题了,我们首先回顾下颜色数的常见做法统计:对每个位置维护一个\(pre_i\),表示与当前位置相同的颜色上一次出现位置。那么我们分讨一下。查询\([l,r]\)得到颜色数,对于\(pre_i<l\)的\(i\)点,显然它就是这个区间内\(a_i\)对应颜色出现的第一个位置,我们......