P2661 信息传递题解

题目描述

有 n 个同学(编号为 1 到 n )正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 i的同学的信息传递对象是编号为Ti的同学。

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

输入格式
共2行。

第1行包含1个正整数 n ,表示 n 个人。

第2行包含 n 个用空格隔开的正整数 T1,T2, … ,Tn , 其中第i个整数Ti代表编号为i的童靴将信息传递给编号为Ti的童靴, Ti <= n, 且Ti ≠ i;

输出格式

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

输入输出样例

输入

5
2 4 2 3 1

输出

3

我在注释里面写的应该很清楚了, 这一题其实就是图的最小环问题, 并使用了并查集将问题简化

#include <bits/stdc++.h>
using namespace std;
int n, ans = INT_MAX;
int a[200010], fa[200010], dis[200010]; //dis数组记录到祖先节点的距离, fa数组记录它的父亲节点, 并会更新为它的祖先节点
//对于i将信息传给a[i], 那么就有一条由a[i]指向i的箭头, 由此构造出一个图, 按此种构造, 每个点入度不会超过1
int getfa(int u) {
    //找到祖先的函数
    //该函数返回祖先, 因为该函数用到了路径压缩算法
    if (fa[u] == u) return u;
    int tmpFa = fa[u]; //注意这里的一个坑, 当两个不同的连通分量合并时, 要先找到单个连通分量的祖先, 并将其保存在一个变量中
    fa[u] = getfa(fa[u]); //这里的赋值是u所在得连通分量的祖先入赘的操作
    dis[u] = dis[u] + dis[tmpFa]; // u到祖先的距离是u到之前连通分量的祖先的距离加上之前的祖先到新祖先的距离
    return fa[u];
}
void my_union(int u, int v) {
    //调用函数, 获得祖先
    int fu = getfa(u);
    int fv = getfa(v);
    if (fu == fv) {
        //这里就说明找到了环, 注意: 找到了环之后就不能连起来, 只是更新答案而已
        ans = min(ans, dis[v] + 1);
    } else {
        //若没有找到环, 那么更新祖先和距离
        fa[u] = fv;
        dis[u] = dis[v] + 1;
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        //并查集的初始化
        fa[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        my_union(i, a[i]);
    }
    cout << ans;
    return 0;
}

附上一篇参考博客题解 P2661 【信息传递】

https://juejin.im/post/5e33ac84e51d4502044ed8c6

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论