【并查集判有向环】[NOIP2015]信息传递

╰半夏微凉° 2024-03-24 11:39 47阅读 0赞

[1023-\[NOIP2015\]信息传递\_2021秋季算法入门班第九章习题：图论 (nowcoder.com)][1023-_NOIP2015_2021_ _nowcoder.com]

题意：

![13a31e8f887c48a38ff2fde6146561b8.png][]

思路：

本来第一反应是给每个点bfs然后看形成环的最小步是多少步

后来发现好像会超时（但是并查集也是n^2的啊，可能是数据水了）

正解是并查集求有向图最小环

只需要不断地加边，维护最小环长度就行

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    using i64 = long long;
    const int mxn=2e6+10;
    const int mxe=2e6+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    
    int n,x,tot=0;
    int f[mxn];
    int find(int x,int &cnt){
        cnt++;
        if(x==f[x]) return x;
        return find(f[x],cnt);
    }
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) f[i]=i;
        int ans=1e9;
        for(int i=1;i<=n;i++){
            cin>>x;
            int cnt=0;
            if(find(x,cnt)==i) ans=min(ans,cnt);
            else f[i]=x;
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[1023-_NOIP2015_2021_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/26077/1023
[13a31e8f887c48a38ff2fde6146561b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/ca16eadd576b495a853990b3c9cf98e1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，47人围观）

还没有评论，来说两句吧...

相关阅读

相关篮球杯【并查集】发现环

[发现环 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn] 题意: ![aa1bcadefde095cbab2818e729c3fa3d.png]

谁践踏了优雅/ 2024年03月25日 10:14/ 0 赞/ 55 阅读

相关【并查集判有向环】[NOIP2015]信息传递

[1023-\[NOIP2015\]信息传递\_2021秋季算法入门班第九章习题：图论 (nowcoder.com)][1023-_NOIP2015_2021_ _nowcod

╰半夏微凉°/ 2024年03月24日 11:39/ 0 赞/ 48 阅读

相关 UVALive - 3644 X-Plosives(并查集判断是否有环)

易爆物（ X-Plosives, LA 3644）有一些简单化合物，每个化合物都由两种元素组成的（每个元素用一个大写字母表示）。你是一个装箱工人，从实验员

╰+哭是因爲堅強的太久メ/ 2024年02月17日 22:22/ 0 赞/ 41 阅读

相关 P2661 [NOIP2015 提高组] 信息传递

P2661 \[NOIP2015 提高组\] 信息传递——有向图相关算法⭐️⭐️⭐️⭐️ 题目描述有 n个同学（编号为 1到 n）正在玩一个信息传递的游戏。在游戏里

柔光的暖阳◎/ 2022年10月27日 02:23/ 0 赞/ 191 阅读

相关并查集 Hdu 1272 (判环)+ Hdu 1213 + Hdu 1232 + Hdu 3172

Hdu 1272 小希的迷宫思路：两点的根节点相同，并且他们又彼此连通，则说明构成环。如果无环且点数-1==边数则说明只有一个连通块 include <cst

我不是女神ヾ/ 2022年09月20日 15:09/ 0 赞/ 205 阅读

相关 HDU 1272(并查集求无向图环)

include <iostream> include <cstring> using namespace std; int s

桃扇骨/ 2022年09月20日 12:42/ 0 赞/ 159 阅读

相关 684 冗余连接（无向图中找环-并查集）

1. 问题描述：树可以看成是一个连通且无环的无向图。给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附

小灰灰/ 2022年09月03日 00:28/ 0 赞/ 129 阅读

相关 Poj 3310 Caterpillar (并查集判环+度)

题意：判断一个给定的图是否满足以下条件： 1.没有环 2.而且存在一条链，图上的所有点均在链上，或者是链上点的邻居。解题思路： 1.要求存在一条链，那么图必须连通，可

r囧r小猫/ 2022年08月27日 03:53/ 0 赞/ 125 阅读

相关（判环-基础并查集）hdu1272 小希的迷宫

传送门：[hdu1272 小希的迷宫][hdu1272] 目录错误代码：正确代码： -------------------- 判断是否能形成环即可。代码wa，还

朱雀/ 2022年04月16日 07:17/ 0 赞/ 195 阅读

相关洛谷 P2661 信息传递（NOIP 提高 2015）

[传送门][Link 1] 本题本来是一个很好的并查集的题（似乎靠的就是并查集），然而蒟蒻我刚刚学习了 tarjan 所以就用 terjan做了一下大概题意

电玩女神/ 2021年11月16日 06:42/ 0 赞/ 267 阅读