Description

Submission

class Solution {
public:
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        vector<vector<int>> next(n);
        
        for(auto& road: roads) {
            next[road[0]].push_back(road[1]);
            next[road[1]].push_back(road[0]);
        }
        
        int ret = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                int total = next[i].size() + next[j].size();
                // if there's a direct path between i and j
                // cout << "before: " << total;
                if(find(next[i].begin(), next[i].end(), j) != next[i].end()) {
                    total -= 1;
                }
                // cout << "after: " << total;
                ret = max(total, ret);
            }
        }
        return ret;
    }
};