【传送门：BZOJ1529】
简要题意：
给出n个储钱罐，给出每个储钱罐的钥匙在哪一个储钱罐里，可以选择用钥匙或者直接砸开储钱罐从而拿到钱，求出最少砸开多少个储钱罐能够将所有储钱罐里的钱
题解：
并查集
原本想用强联通，结果MLE
如果第i个储钱罐的钥匙在第j个储钱罐里，则j连向i
显然对于一个环，只要随便砸掉其中一个，就可以将整个环拿到
而且对于这个环连出去的环或者点都可以被拿到
注意因为每个点只能被一个点连，而一个点可以连很多个点，所以直接并查集就可以了
%%Hanks_o，据说这是什么外向树
参考代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std; struct node { int x,y; }a[1100000];int len,last[1100000]; int fa[1100000]; int findfa(int x) { if(fa[x]!=x) fa[x]=findfa(fa[x]); return fa[x]; } int k[1100000]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&k[i]); a[++len].x=k[i]; a[len].y=i; } for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=len;i++) { int bx=a[i].x,by=a[i].y; if(bx!=by) { int fx=findfa(bx),fy=findfa(by); fa[fy]=fx; } } int ans=0; for(int i=1;i<=n;i++) if(fa[i]==i) ans++; printf("%d ",ans); return 0; }