题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1529
因为一个存钱罐只能被一个其他的罐打开，也就是一个点的入度只能为1
所以它就可以和前一个合并起来，用并查集搞一搞就好了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include<bits/stdc++.h> #define MAXN 1000010 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } int fa[MAXN],n,x,y,ans; int getroot(int x){ if(fa[x]==x)return x; return fa[x]=getroot(fa[x]); } int main(){ n=rd(); for(int i=1; i<=n; i++)fa[i]=i; for(int i=1; i<=n; i++)x=rd(),x=getroot(x),y=getroot(i),fa[y]=x; for(int i=1; i<=n; i++)ans+=fa[i]==i; printf("%d\n",ans); return 0; } |
