leetcode::maximum_good_people_based_on_statements::Solution类 参考

#include <leetcode.h>

静态 Public 成员函数
static pair< int, unordered_map< int, bool > >	dfs (vector< vector< int > > &statements, unordered_map< int, bool > um, queue< msg > que)
static int	maximumGood (vector< vector< int > > &statements)

详细描述

在文件 leetcode.h 第 678 行定义.

成员函数说明

dfs()

pair< int, unordered_map< int, bool > > leetcode::maximum_good_people_based_on_statements::Solution::dfs ( vector< vector< int > > & statements, unordered_map< int, bool > um, queue< msg > que )

static

在文件 leetcode.cpp 第 1528 行定义.

                                                                                                                                      {
            int maximum     = 0;
            bool contradict = false;
            while(!que.empty()) {
                auto current = que.front();
                que.pop();
                if(um.contains(current.person)) {
                    //已经存在
                    if(um[current.person] != current.good) {
                        //矛盾
                        return pair<int, unordered_map<int, bool>>(0, {});
                    }
                } else {
                    um.insert(pair(current.person, current.good));
                }
                if(current.good) {
                    //是好人
                    for(int j = 0; j < statements.size(); j++) {
                        if(statements[current.person][j] != 2 && j != current.person) {
                            auto nmsg = msg(j, statements[current.person][j] == 1);
                            if(um.contains(nmsg.person)) {
                                //已经有了
                                if(um[nmsg.person] != nmsg.good) {
                                    //矛盾
                                    contradict = true;
                                    return pair<int, unordered_map<int, bool>>(0, {});
                                }
                            } else {
                                //还没有
                                que.push(nmsg);
                            }
                        }
                    }
                }
            }
            if(!contradict) {
                //不矛盾
                auto dup = unordered_map<int, bool>();
                for(int i = 0; i < statements.size(); i++) {
                    if(dup[i]) {
                        continue;
                    }
                    if(!um.contains(i)) {
                        bool all2 = true;
                        for(auto v: statements[i]) {
                            if(v != 2) {
                                all2 = false;
                            }
                        }
                        if(all2) {
                            um.insert(pair(i, true));
                            continue;
                        }
                        auto nque = queue<msg>();
                        nque.push(msg(i, true));
                        auto ans = dfs(statements, um, nque);
                        maximum  = max(maximum, ans.first);
                        for(auto it: ans.second) {
                            if(it.second) {
                                dup.insert(it);
                            }
                        }
                    }
                }
 
                int good_count = 0;
                for(auto i: um) {
                    if(i.second) {
                        good_count++;
                    }
                }
                maximum = max(maximum, good_count);
            }
            return pair(maximum, um);
        }

引用了 dfs().

被这些函数引用 dfs() , 以及 maximumGood().

maximumGood()

int leetcode::maximum_good_people_based_on_statements::Solution::maximumGood ( vector< vector< int > > & statements )

static

在文件 leetcode.cpp 第 1507 行定义.

                                                                 {
            int maximum = 0;
            auto dup    = unordered_map<int, bool>();
            for(int i = 0; i < statements.size(); i++) {
                if(dup[i]) {
                    continue;
                }
                const auto um = unordered_map<int, bool>();
                auto que      = queue<msg>();
                que.push(msg(i, true));
                auto ans = dfs(statements, um, que);
                maximum  = max(maximum, ans.first);
                for(auto it: ans.second) {
                    if(it.second) {
                        dup.insert(it);
                    }
                }
            }
            return maximum;
        }

引用了 dfs().

被这些函数引用 leetcode::maximum_good_people_based_on_statements::TEST() , 以及 leetcode::maximum_good_people_based_on_statements::TEST().

---

该类的文档由以下文件生成:

• leetcode.h
• leetcode.cpp