首页 > 代码库 > BZOJ 1529 [POI2005]ska Piggy banks（并查集）
BZOJ 1529 [POI2005]ska Piggy banks（并查集）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1529
【题目大意】
给出一张n个点n条边的有向图，问选取几个点为起点可以遍历全图
【题解】
由于是n条边，因此图为基环森林，选取环上点一定可以到达连通块内所有点，
因此只要统计连通块个数即可。
【代码】
#include <cstdio>#include <algorithm>using namespace std;const int N=1000100;int f[N],n;int sf(int x){return f[x]==x?x:f[x]=sf(f[x]);}int main(){ while(~scanf("%d",&n)){ for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=n;i++){ int x; scanf("%d",&x); f[sf(i)]=sf(x); }int ans=0; for(int i=1;i<=n;i++)if(sf(i)==i)ans++; printf("%d\n",ans); }return 0;}BZOJ 1529 [POI2005]ska Piggy banks（并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。