F - Number of Connected Components UVALive - 7638 (并查集 + 思维)

时间:2022-05-23 05:31:19

题目链接:https://cn.vjudge.net/contest/275589#problem/F

题目大意:就是给你n个数,如果说两个数之间的gcd!=1,那么就将这两个点连起来,问你最终这些点能形成几块

具体思路:首先,我们可以讲所有数的倍数给标记出来,然后如果有一个数是 6,我们就把2 3 6 全部指向6,这样的话,每当我们找到一个数,我们就把这个数和他的素因子连起来(并查集),往小的地方连,然后最后看一下输入的n个数是不是标记的自己,如果是自己那么这肯定是一个块,如果不是标记的自己,就证明他所在的块已经被算过了(这也太暴力了...)

AC代码:

 #include<bits/stdc++.h>
using namespace std;
# define inf 0x3f3f3f3f
# define ll long long
const int maxn = +;
int a[maxn],vis[maxn],father[maxn];
vector<int>q[maxn];
void init()
{
for(int i=; i<=maxn; i++)
{
for(int j=i*; j<=maxn; j+=i)
{
q[j].push_back(i);
}
}
}
int Find(int t)
{
return t==father[t]?t:father[t]=Find(father[t]);
}
void cal(int t1,int t2)
{
int x1=Find(t1);
int y1=Find(t2);
if(x1!=y1)
{
if(x1>y1)father[x1]=y1;
else father[y1]=x1;
}
}
int main()
{
init();
int T;
scanf("%d",&T);
int Case=;
while(T--)
{
int n;
scanf("%d",&n);
for(int i=; i<=maxn; i++)
{
father[i]=i;
}
memset(vis,,sizeof(vis));
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
int len=q[a[i]].size();
for(int j=; j<len; j++)
{
cal(a[i],q[a[i]][j]);
}
}
ll ans=;
for(int i=; i<=n; i++)
{
if(a[i]==)
{
ans++;
continue;
}
int t=Find(a[i]);
if(vis[t])continue;
vis[t]=;
ans++;
}
printf("Case %d: %lld\n",++Case,ans);
}
return ;
}