F - Number of Connected Components UVALive - 7638 -素筛-并查集

F - Number of Connected Components

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000100
map<int,bool>vis;
vector<int>save;
bool isprime[maxn];
int t,n,a[maxn],fa[maxn],ans,len,tp;
int fond(int x)
{
    if(fa[x]==-1)return x;
    else return fa[x]=fond(fa[x]);
}
void unon(int x,int y)
{
    int xx=fond(x);
    int yy=fond(y);
    if(xx!=yy)
    {
        if(xx<yy)
            fa[xx]=yy;
        else
            fa[yy]=xx;
    }
}
void prime()
{
    isprime[0]=isprime[1]=1;
    for(int i=2; i<sqrt(maxn); i++)
        for(int j=i*i; j<maxn; j+=i)
            isprime[j]=1;
    for(int i=1; i<maxn-11; i++)
        if(!isprime[i])
            save.push_back(i);
}
int main()
{
    prime();
    len=save.size();
    scanf(\"%d\",&t);
    for(int q=1; q<=t; q++)
    {
        vis.clear();
        memset(fa,-1,sizeof(fa));
        ans=0;
        scanf(\"%d\",&n);
        for(int i=1; i<=n; i++)
        {
            scanf(\"%d\",&a[i]);
            vis[a[i]]=1;
            if(a[i]==1)
            {
                ans++;
                continue;
            }
            tp=a[i];
            for(int j=0; j<len; j++)
            {
                if(tp%save[j]==0)
                {
                    while(tp%save[j]==0)
                        tp/=save[j];
                    unon(a[i],save[j]);
                }
                else if(isprime[tp]==0)
                {
                    unon(a[i],tp);
                    break;
                }
                else if(tp==1)break;
            }
        }
        for(int i=1; i<=n; i++)
        {
            if(a[i]==1)continue;
            fond(a[i]);
            if(fa[a[i]]==-1&&vis[a[i]]==1)
            {
                vis[a[i]]=0;
                ans++;
            }
        }
        printf(\"Case %d: %d\\n\",q,ans);
    }
    return 0;
}