Preprocessing to speedup the calculation

LC 1761. Minimum Degree of a Connected Trio in a Graph

This is a weekly contest of Feb 13, 2021

It is a graph problem, however, the critical idea is using preprocessing to reduce the complexity.

Idea

We can straightforwardly checking the qualified tuple (i, j, k) and get the results directly. Pseudo code is
for tuple i, j, k if I, j, k is a connected graph.
res = min(res, cnt[I]+ cnt[j] + cnt[k]-6)

We subtract 6 to get rid of over counting. Thinking about ABC, for each node it will have two neighbors, those two neighbors shoud not be counted.

Reference code

// time complexity: O(n^3)
int am[401][401];//adjacency matrix
int cnt[401];
class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>>& edges) {
        memset (am, 0, sizeof am);
        memset (cnt, 0, sizeof cnt);
        for (auto e: edges) {
            int u = e[0], v = e[1];
            am[u][v] = am[v][u] = 1;
            cnt[u]++; cnt[v]++;
        }
        int ret = INT_MAX;
        for (int i = 1; i <=n-2 ; ++i) {
            for (int j = i + 1; j <= n -1; ++j) {
                for (int k = j + 1; k <=n; ++k) {
                    if ( am[i][j] && am[j][k] && am[i][k] ){
                        ret = min(ret, cnt[i] + cnt[j] + cnt[k] - 6); 
                    }
                }
            }
        }
        return ret == INT_MAX ? -1 : ret;
    }
};