acwing 517. 信息传递

地址 https://www.acwing.com/problem/content/description/519/

有 n 个同学（编号为 1 到 n）正在玩一个信息传递的游戏。

在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 TiTi 的同学。 

游戏开始时，每人都只知道自己的生日。

之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。

当有人从别人口中得知自己的生日时，游戏结束。

请问该游戏一共可以进行几轮？

输入格式
输入共 2 行。 

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

第 2 行包含 n 个用空格隔开的正整数T1,T2,…,Tn，其中第 i 个整数 Ti 表示编号为 i 的同学的信息传递对象是编号为 Ti 的同学，Ti ≤n 且 Ti ≠i。 

数据保证游戏一定会结束。

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

数据范围
n≤200000
输入样例：
5
2 4 2 3 1
输出样例：
3

解法

每个人看做点 通讯的途径看做边的话 这里就是求最短的环。

应该可以使用搜索的方式获取最短的环

我们这里没使用这种方式 而是使用tarjan求环

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int maxn = 2e5 + 7;
vector<int> E[maxn];
int vis[maxn];
int dfn[maxn], low[maxn], tot, n, ans = maxn;
stack<int> s;

void tarjan(int x)
{
    low[x] = dfn[x] = ++ tot;
    s.push(x); vis[x] = 1;

    for (int i = 0; i < E[x].size(); i++) {
        int v = E[x][i];
        if (!dfn[v]) {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        }
        else if (vis[v]) {
            low[x] = min(low[x], dfn[v]);
        }
    }

    if (low[x] == dfn[x]) {
        int cnt = 0;
        while (1) {
            int now = s.top();
            s.pop();
            vis[x] = 0;
            cnt++;
            if (now == x) break;
        }
        if (cnt > 1) ans = min(ans, cnt);
    }

}

int main()
{
    scanf("%d",&n );
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        E[i].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i])
            tarjan(i);
    }

    cout << ans << endl;

    return 0;
}

还可以考虑使用并查集的办法 找到最小的并查集即可

#include <iostream>

using namespace std;


const int N = 200000+1000;
int fa[N],n,m,i,j,k,cnt,ans = 1e9;

int find(int  x)
{
    cnt++;
    return fa[x]==x?x:find(fa[x]);
}


int main(){
    cin >> n;
    for(int i = 1;i <= n;i++)
        fa[i] = i;
    for(int i = 1;i <= n;i++){
        int x;
        cin >> x;
        cnt = 0;
        if(find(x) == i)
            ans = min(ans,cnt);
        else 
            fa[i] = x;
    }
    
    cout << ans;    
    return 0;
}