1761. Minimum Degree of a Connected Trio in a Graph

You are given an undirected graph. You are given an integer n which is the number of nodes in the graph and an array edges, where each edges[i] = [ui, vi] indicates that there is an undirected edge between ui and vi.

A connected trio is a set of three nodes where there is an edge between every pair of them.

The degree of a connected trio is the number of edges where one endpoint is in the trio, and the other is not.

Return the minimum degree of a connected trio in the graph, or -1 if the graph has no connected trios.

class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>> &edges) {
        vector<set<int>> nears(n + 1);
        vector<int> countOfNears(n + 1);
        for(auto &edge : edges) {
            nears[min(edge[0], edge[1])].insert(max(edge[0], edge[1]));
            countOfNears[edge[0]]++;
            countOfNears[edge[1]]++;
        }
        int res = INT_MAX;
        for(auto n1 = 1; n1 <= n; n1++)
            for(auto n2 = nears[n1].begin(); n2 != nears[n1].end(); n2++)
                for(auto n3 = next(n2); n3 != nears[n1].end(); n3++)
                    if(nears[*n2].count(*n3))
                        res = min(res, countOfNears[n1] + countOfNears[*n2] + countOfNears[*n3]);
        return res == INT_MAX ? -1 : res - 6;
    }
};

class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>> &edges) {
        vector<vector<int>> near(n + 1);
        vector<vector<bool>> isConnected(n+1, vector<bool>(n+1, false));
        for(auto &edge : edges) {
            near[edge[0]].push_back(edge[1]);
            near[edge[1]].push_back(edge[0]);
            isConnected[edge[0]][edge[1]] = true; isConnected[edge[1]][edge[0]] = true;
        }

        int res = INT_MAX;
        for(int x = 1; x <= n; ++x) {
            sort(near[x].begin(),near[x].end(),[&](int i, int j) { return near[i].size() < near[j].size(); });
            if(near[x].size() < 2 || (int)near[near[x][0]].size() + (int)near[near[x][1]].size() + (int)near[x].size() >= res) continue;
            for(auto y = begin(near[x]); y != end(near[x]); ++y) {
                if(next(y) != end(near[x]) && (int)near[x].size() + (int)near[*y].size() + (int)near[*(next(y))].size() >= res) break;
                for(auto z = next(y); z != end(near[x]); ++z) {
                    if(isConnected[*y][*z])
                        res = min(res, (int)near[x].size() + (int)near[*y].size() + (int)near[*z].size());
                }
            }
        }

        return res == INT_MAX ? -1 : res - 6;
    }
};