1615. 最大网络秩

这道题是我思考有问题了，做了好多遍，并没有很困难。先确定最大数组和次大数组没问题，两种情况，如果最大数组只有一个或最大数组大于一个。如果最大数组大于一个，就用两个for遍历最大数组。名字起的不好，第二大的竟然叫minor。

有的教程写的如果是完全图就不用算了，但那个是特殊情况，不考虑不会对结果有影响

class Solution {
public:
class Node {
 public:
  int name_;
  int degree_;
  unordered_set next_node_set;
  Node(int name) : name_(name), degree_(0) {}
};

class Graph {
 public:
  unordered_map node_;
  Graph(int n, const vector>& a) {
    for (int i = 0; i < n; i++) node_[i] = new Node(i);

    for (int i = 0; i < (int)a.size(); i++) {
      node_[a[i][0]]->next_node_set.insert(a[i][1]);
      node_[a[i][0]]->degree_++;
      node_[a[i][1]]->next_node_set.insert(a[i][0]);
      node_[a[i][1]]->degree_++;
    }
  }

  ~Graph() {
    for (auto pairr : node_) delete pairr.second;
  }

 private:
  Graph(const Graph&);
  Graph(Graph&&);
  Graph& operator=(Graph);
};
int maximalNetworkRank(int n, const vector>& roads) {
  Graph graph(n, roads);
  vector major_vec, minor_vec;
  int major_degree = 0, minor_degree = 0;
  for (auto node : graph.node_) {
    if (node.second->degree_ > major_degree) {
      swap(minor_degree, major_degree);
      swap(minor_vec, major_vec);

      major_degree = node.second->degree_;
      major_vec.clear();
      major_vec.emplace_back(node.first);
    } else if (node.second->degree_ == major_degree)
      major_vec.emplace_back(node.first);
    else if (node.second->degree_ > minor_degree) {
      minor_degree = node.second->degree_;
      minor_vec.clear();
      minor_vec.emplace_back(node.first);
    } else if (node.second->degree_ == minor_degree)
      minor_vec.emplace_back(node.first);
  }

  if (1 == major_vec.size()) {
    for (auto next_node : minor_vec) {
      if (graph.node_[next_node]->next_node_set.find(major_vec.front()) ==
          graph.node_[next_node]->next_node_set.end())
        return major_degree + minor_degree;
    }
    return major_degree + minor_degree - 1;
  }else {
    for (int i = 0; i < static_cast(major_vec.size()); ++i) {
      for (int j = i + 1; j < static_cast(major_vec.size()); ++j) {
        if (graph.node_[major_vec[i]]->next_node_set.find(major_vec[j]) ==
            graph.node_[major_vec[i]]->next_node_set.end())
          return major_degree * 2;
      }
    }
    return major_degree * 2 - 1;
  }
}

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75