求解有向图中的最大环问题

本文主要是介绍求解有向图中的最大环问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接
思路：
主要分为两种情况：
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);
            }
        }
    }
};

这篇关于求解有向图中的最大环问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！