题目链接
思路:
主要分为两种情况:
1.两个人互相喜欢,那么就可以在这两个人两边各自不停地添加座位,选择一个最长的链即可。然后把所有两个人互相喜欢得到的链拼在一起是第一种最大的选法。
2.选出一个长度大于等于三的有向环,这里使用hash_map来保存之前节点的深度,一旦找到一个新的节点他的深度保存过,那么相减+1就是一个环,遍历所有的环取最大就是另外一种选法。
代码如下:
class Solution { int n,a,b,tmp=0; int ret = 0; vector<vector<int>>adj; vector<int>vis = vector<int>(100005,0); public: int maximumInvitations(vector<int>& favorite) { n = favorite.size(); vector<int>v; vector<vector<int>>_adj(n,v); adj = _adj; for(int i = 0;i<n;i++){ b = favorite[i]; adj[b].push_back(i); } //首先计算两个人互相喜欢的情况 for(int i = 0;i<n;i++){ b = favorite[i]; if(!vis[i] && favorite[b] == i){ vis[i] = 1; vis[b] = 1; int n1 = dfs(i,0); int n2 = dfs(b,0); ret += (n1+n2+2); } } //计算最长环 for(int i = 0;i<n;i++){ if(!vis[i]){ unordered_map<int,int>info; tmp = 0; longest_circle(i,1,info); ret = max(tmp,ret); } } return ret; } private: int dfs(int id,int depth){ int res = depth; for(int i = 0;i<adj[id].size();i++){ int next = adj[id][i]; if(!vis[next]){ vis[next] = 1; res = max(res,dfs(next,depth+1)); } } return res; } void longest_circle(int id,int depth,unordered_map<int,int>& info){ vis[id] = 1; info[id] = depth; for(int i = 0;i<adj[id].size();i++){ int next = adj[id][i]; if(info[next] != 0){ tmp = max(tmp,info[id]-info[next]+1); }else{ longest_circle(next,depth+1,info); } } } };