字节跳动第四题AC
我的是那个糖果的题，两点最大公约数大于2就连通。
讲思路吧，AC代码在回帖里。
首先预处理每个数的质因子，这样我们就可以根据质因子判断哪些点是连通的了，因为公约数大于2必定会有相同的质因子。
处理完之后就是一个最大连通图的裸题了。
#字节跳动##笔试题目#
2019-08-26 10:30 已编辑 湖南大学 golang
关注
全部评论
米迦勒mi
作业帮_算法工程师
最大连通图咋做的 我用并查集只能过70% 剩下的时间不行
雷男有西 楼主
楼主 湖南大学 golang
const LL mod = 1000000007;
const int maxn = 200005;
int n,m,k;
int a[maxn],dp[maxn];
int vis[maxn],vv[maxn];
vector<int > vc[maxn],vs[maxn];
int ans;
void bfs(int u){
vv[u] = 1;
int z = a[u];
int len = vc[z].size();
for(int i = 0;i<len;i++){
int v = vc[z][i];
int le = vs[v].size();
for(int j = 0;j<le;j++){
int b = vs[v][j];
if(vv[b] == 0){
ans++;
bfs(b);
}
}
}
}
int main()
{
cin>>n;
for(int i = 0;i<n;i++){
int x;
scanf("%d",&a[i]);
x = a[i];
if(vis[x] == 1) {
int le = vc[x].size();
for(int j=0;j<le;j++){
int v = vc[x][j];
vs[v].push_back(i);
}
continue;
}
vis[x] = 1;
int y = x;
for(int j =2;j*j<=y;j++){
if(y%j==0){
vc[x].push_back(j);
while(y%j==0){
y/=j;
}
}
}
if(y!=1) vc[x].push_back(y);
int len = vc[x].size();
for(int j=0;j<len;j++){
int v = vc[x][j];
vs[v].push_back(i);
}
}
int ll = vs[2].size();
int maxx = 0;
for(int i = 0;i<n;i++){
if(vv[i] == 0){
ans = 1;
bfs(i);
maxx = max(ans,maxx);
}
}
cout<<maxx<<endl;
return 0;
}
菜鸡_如我
复旦大学 C++
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
if (b == 0)return a;
else return gcd(b, a%b);
}
int flag[1000];
int getFather(int x) {
if (flag[x] == -1)return x;
else {
int tmp = getFather(flag[x]);
flag[x] = tmp;
return tmp;
}
}
int main() {
int n;
cin >> n;
vector<int>sugar(n);
vector<int>nums(n);
for (int i = 0; i < n; i++) {
cin >> sugar[i];
flag[i] = -1;
nums[i] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (gcd(sugar[i], sugar[j]) > 1) {
int a = getFather(i);
int b = getFather(j);
if (a != b) {
flag[a] = b;
nums[b] += nums[a];
}
}
}
}
int res = 0;
for (int i = 0; i < n; i++)
res = max(res, nums[i]);
cout << res << endl;
return 0;
}
我用并查集做的，也是70%
2020冲鸭~
老虎集团_ESOP后端研发_后端研发
楼主求题目
相关推荐
投递腾讯等公司10个岗位 >
