题解 P7299 【[USACO21JAN] Dance Mooves S】

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

管理员小哥哥辛苦！