本来以为是tarjan缩点……但是64MB的空间根本不足以存下原图和缩点后的新图。所以呢……并查集= =
orz hzwer
MLE的tarjan：
/**************************************************************
Problem: 1529
User: Tunix
Language: C++
Result: Memory_Limit_Exceed
****************************************************************/ //BZOJ 1529
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
const int N=; void read(int &v){
v=;int sign=; char ch=getchar();
while(ch<'' || ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){v=v*+ch-''; ch=getchar();}
v*=sign;
}
/********************tamplate*******************/
int dfn[N],low[N],dfs_clock,SCC=,belong[N],n;
int head[N],to[N],next[N],cnt;
void ins(int x,int y){
to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt;
}
int t[N],ne[N],h[N];
void add(int x,int y){
t[++cnt]=y; ne[cnt]=h[x]; h[x]=cnt;
}
bool inst[N];
int st[N],top=;
void tarjan(int x){
int y;
dfn[x]=low[x]=++dfs_clock;
st[top++]=x;
inst[x]=;
for(int i=head[x];i;i=next[i]){
y=to[i];
if (!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if (inst[y]) low[x]=min(low[x],dfn[y]);
}
if (dfn[x]==low[x]){
++SCC;
for(y=;y!=x;){
y=st[--top];
inst[y]=;
belong[y]=SCC;
}
}
}
int in[N];
void rebuild(){
F(x,,n)
for(int i=head[x];i;i=next[i])
if (belong[x]!=belong[to[i]]){
add(belong[x],belong[to[i]]);
in[belong[to[i]]]++;
}
}
/***********************************************/ int main(){
#ifndef ONLINE_JUDGE
freopen("1529.in","r",stdin);
#endif
read(n);
int x;
F(i,,n){
read(x);
ins(x,i);
}
F(i,,n) if (!dfn[i]) tarjan(i);
rebuild();
int ans=;
F(i,,SCC) if(in[i]==) ans++;
printf("%d\n",ans);
return ;
}
并查集：
/**************************************************************
Problem: 1529
User: Tunix
Language: C++
Result: Accepted
Time:908 ms
Memory:4712 kb
****************************************************************/ //BZOJ 1529
#include<cstdio>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
const int N=; void read(int &v){
v=;int sign=; char ch=getchar();
while(ch<'' || ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){v=v*+ch-''; ch=getchar();}
v*=sign;
}
int fa[N],n;
int getfather(int x){
if (fa[x]!=x) fa[x]=getfather(fa[x]);
return fa[x];
}
int main(){
read(n);
int x;
F(i,,n) fa[i]=i;
F(i,,n){
read(x);
int f1=getfather(i),f2=getfather(x);
if (f1!=f2) fa[f1]=f2;
}
int ans=;
F(i,,n) if (fa[i]==i) ans++;
printf("%d\n",ans);
return ;
}