文中没给代码的后期补上，有AC的同学欢迎评论发一下代码
牛客讨论帖 /discuss/98663?type=2&order=0&pos=5&page=1
这道题考察的是并查集(或者DFS)，看代码前请先了解一下并查集
并查集解释
上面那个链接的博客里面代码有点错误，错误之处在评论中有指出
并查集思路：
#include <stdio.h>#define N 100020int friends[N];//每个人所属的连通分量，即构成朋友树时每个人的父节点int rank[N];//连通分量的权值，即朋友树的大小int res;void init(int n)//初始化initialization{for(int i=0;i<n;i++){friends[i]=i;rank[i]=0;}}int findRoot(int x)//寻找x所属的朋友树的根节点{//一直向上遍历寻找根节点while(x != friends[x])x = friends[x];return x;}void connect(int x,int y){int xRoot = findRoot(x);int yRoot = findRoot(y);if(xRoot == yRoot)return ;//判断树高，小树并在大树下if(rank[xRoot] < rank[yRoot])friends[xRoot]=yRoot;else{friends[yRoot] = xRoot;if(rank[xRoot]==rank[yRoot])//两树高相等，合并后树高+1rank[xRoot]++;}--res;}int main(){int n;init(N);//初始化scanf("%d",&n);res = n;for(int i=1;i<=n;i++){int t;while(~scanf("%d",&t)){if(t == 0)break;connect(i,t);}}printf("%d",res);/*1005 3 08 4 09 09 03 007 9 009 7 0*/return 0;}
DFS思路：
#include <iostream>#include <vector>using namespace std;int n;int res;void dfs(vector<vector<int>>& friends, int x, int y,vector<vector<bool>>& mark){if(x >= friends.size() || y >= friends[0].size() || x < 0 || y < 0)return;if(mark[x][y] == true)return;if(friends[x][y] == 0){mark[x][y] = true;return;}// 对于已经搜索过的点要进行标记mark[x][y] = true;res--;for(int j=1; j<n; j++){dfs(friends, x, j, mark);}}void minM(vector<vector<int>>& friends) {if(friends.empty())return;res = n;vector<vector<bool>> vecMark(friends.size(),vector<bool>(friends[0].size(),false));// 定义标记数组//开始搜索for(int i = 1;i < friends.size();i++){for(int j = 1;j < friends[0].size();j++){if(vecMark[i][j] == true)continue;if(friends[i][j] == 0){vecMark[i][j] = true;continue;}dfs(friends, i, j, vecMark);}}cout << num << endl;}int main(){cin >> n;vector<vector<int>> friends(n+1, vector<int>(n+1,0));int temp = 0;for(int i=1; i<=n; i++){int j = 1;while(cin>>temp){if(temp == 0)break;friends[i][j] = temp;j++;}}minM(friends);return 0;}
思路：
本来是在全局序列之中求最长上升子序列,但是因为是重复的序列，
其实只需在第一个序列之中求最长上升序列，并且其中的最大元素在后面的每个序列之中一定存在，最后加上b-1(b为重复序列个数)
ans[] 存储给定序列
tmp[i] 表示从第0位到第i位的最长子序列个数
#include <iostream>#include <vector>#include <algorithm>using namespace std;int main(){int a,b;scanf("%d%d", &a, &b);vector<int> ans(a, 0),tmp(a,1);for (int i = 0;i<a;i++){scanf("%d", &ans[i]);}for (int i = 1;i<a;i++){for (int j = 0;j<i;j++){if (ans[i]>=ans[j]){tmp[i] = max(tmp[i], tmp[j] + 1);}}}cout << *max_element(tmp.begin(), tmp.end())+b-1;return 0;}
如果觉得《字节跳动校园招聘研发岗位第二次笔试-.08.25》对你有帮助，请点赞、收藏，并留下你的观点哦！
