Java教程

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

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

题目链接
思路:
主要分为两种情况:
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);
            }
        }
    }
};
这篇关于求解有向图中的最大环问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!