自动搬运

查看原文

来自洛谷，原作者为

	Skies **

搬运于2025-08-24 22:28:33，当前版本为作者最后更新于2021-01-28 20:21:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本文语言较为生动，容易理解，适合像我一样的菜鸡

题面分析

我们考虑，在经过k次变换（k分钟）后，每头牛会途径某些点到达另一个点，假如其中有一头好看的牛叫A，A从x位置走到了y位置，而另一头牛B，从z走到了x，那么再经过一轮，B也会走到y位置。

也就是说

B的运动轨迹将会和A一样，只不过是落后k分钟罢了

同时，B经过的点也和A一样

于是乎

像A , B一样的，有相同运动轨迹的牛，将会有一群（当然一群里面可能也只有一只）

而这群牛在k分钟内的运动轨迹将会构成一个环

用并查集维护这个环

我们再用vector来记录每个点途径的点，然后

对于同一个环内（同一牛群），用set来统计每个点的途径点总共有多少个，设为x

环内的每一头牛能经过点的个数，就是x.

讲到这里，思路就非常明晰了，尝试自己写写吧！

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k;
int a[N];
int fa[N],si[N];
void init()
{
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
		a[i]=i;
	}
}
int get(int x)
{
	if(fa[x]==x)return x;
	return fa[x]=get(fa[x]);
}
vector<int >vc[N];
int cx[N],cy[N];
set<int> ans[N];

void out()
{
	for(int i=1;i<=n;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}
int main()
{
	
	cin>>n>>k;
	init();
	for(int i=1;i<=k;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		
		swap(a[x],a[y]);
		vc[a[x]].push_back(x);//记录途径点
		vc[a[y]].push_back(y);//同上
	}
	for(int i=1;i<=n;i++)
	{
		vc[i].push_back(i);//加上他们的起点点
	}
	for(int i=1;i<=n;i++)
	{
	    int x=get(i),y=get(a[i]);//把这两个点放到同一个牛群中
	    fa[x]=y;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<vc[a[i]].size();j++)
		{
			ans[get(a[i])].insert(vc[a[i]][j]);//统计每个点的途径点总共有多少个
		}
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d\n",ans[get(i)].size());//不同途径点的个数即答案
	}
	return 0;
}

管理员小哥哥辛苦！