专栏文章

题解：P2661 [NOIP2015 提高组] 信息传递

QQfaiser
P2661题解参与者 19已保存评论 21

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
21 条
当前快照
1 份
快照标识符
@miqlm5br
此快照首次捕获于
2025/12/04 06:48
3 个月前
此快照最后确认于
2025/12/04 06:48
3 个月前
查看原文

solution

题意就是求有向图中的最小环。可以用并查集处理环。
假设建立一条 aa 到 bb 的有向边时，更新 aa 祖先结点，若两点祖先相同则说明有环，环的大小是两点到祖先结点的距离和加一，距离边找祖先边处理即可。

code

CPP
#include<bits/stdc++.h>
using namespace std;
int n, fa[200005], ans=0x3f3f3f, cnt;
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, t; i<=n; cnt=0, i++)
		cin >> t,
		find(t)==i?ans=min(ans, cnt):fa[i]=t;
	cout << ans;
	return 0;
}

评论

共 21 条评论，欢迎与作者交流。

正在加载评论...