本文共 1252 字，大约阅读时间需要 4 分钟。
本来是想做强连通分量缩点的题
然而1000000不可搞
于是并查集秒
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #define rre(i,r,l) for(int i=(r);i>=(l);i--)14 #define re(i,l,r) for(int i=(l);i<=(r);i++)15 #define Clear(a,b) memset(a,b,sizeof(a))16 #define inout(x) printf("%d",(x))17 #define douin(x) scanf("%lf",&x)18 #define strin(x) scanf("%s",(x))19 #define LLin(x) scanf("%lld",&x)20 #define op operator21 #define CSC main22 typedef unsigned long long ULL;23 typedef const int cint;24 typedef long long LL;25 using namespace std;26 void inin(int &ret)27 {28 ret=0;int f=0;char ch=getchar();29 while(ch<'0'||ch>'9'){ if(ch=='-')f=1;ch=getchar();}30 while(ch>='0'&&ch<='9')ret*=10,ret+=ch-'0',ch=getchar();31 ret=f?-ret:ret;32 }33 int fa[1000010],n;34 int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]);}35 int CSC()36 {37 inin(n);re(i,1,n)fa[i]=i;38 re(i,1,n)39 {40 int x;inin(x);41 int q=find(i),w=find(x);42 if(q!=w)fa[q]=w;43 }44 int ans=0;45 re(i,1,n)if(fa[i]==i)ans++;46 printf("%d",ans);47 return 0;48 }
转载于:https://www.cnblogs.com/HugeGun/p/5176248.html