Solution 1:

We can reason as follows.

• Let $v$ be some vertex of the graph with the minimum degree. If the optimal friendship group contains $v$, then the group is a subset of the connected component of $v$. Thus, such a friendship group can have strength at most $s$ equal to the degree of $v$ times the size of the connected component of $v$. The connected component of $v$ itself is a friendship group with strength $s$ as $v$ has minimum degree, so the highest strength of a friendship group containing $v$ is $s$.
• If the optimal friendship group doesn't contain $v$, we can remove $v$ from the graph.

We can repeatedly identify the minimum degree vertex $v$ of the graph, update the answer to be at least $s$, and then remove $v$ in $O(M+N)$ time. However, computing connected components after every vertex removal naively takes $O(NM)$ time. We can speed this by reversing the sequence of vertex removals (so that we want to maintain connected components after adding instead of removing a vertex), and then using a Disjoint Set Union data structure. The time complexity is $O(M\alpha(N))$ (or $O(M\log M)$ if a set is used to identity and remove the minimum degree vertex).

Timothy Qian's code:

#include <bits/stdc++.h>
 
using namespace std;
 
struct DSU {
  vector<int> e;
 
  DSU(int n) { e = vector<int>(n, -1); }
 
  int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
 
  bool same_set(int a, int b) { return get(a) == get(b); }
 
  int size(int x) { return -e[get(x)]; }
 
  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) return false;
    if (e[x] > e[y]) swap(x, y);
    e[x] += e[y];
    e[y] = x;
    return true;
  }
};
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n);
  vector<int> deg(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
    ++deg[u];
    ++deg[v];
  }
  set<array<int, 2>> vertices;
  for (int i = 0; i < n; ++i) {
    vertices.insert({deg[i], i});
  }
  vector<int> order;
  vector<int> degrees;
  vector<bool> active(n, true);
  auto remove = [&]() {
    auto top = *vertices.begin();
    int u = top[1];
    int degree = top[0];
    order.push_back(u);
    degrees.push_back(degree);
    active[u] = false;
    for (int v : g[u]) {
      if (active[v]) {
        vertices.erase({deg[v], v});
        --deg[v];
        vertices.insert({deg[v], v});
      }
    }
    vertices.erase({deg[u], u});
  };
  for (int i = 0; i < n; ++i) {
    remove();
  }
  reverse(order.begin(), order.end());
  reverse(degrees.begin(), degrees.end());
  active.assign(n, false);
  DSU dsu(n);
  int mx = 1;
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    int u = order[i];
    active[u] = true;
    for (int v : g[u]) {
      if (active[v]) {
        dsu.unite(u, v);
        mx = max(mx, dsu.size(u));
      }
    }
    ans = max(ans, 1ll * mx * degrees[i]);
  }
  cout << ans << '\n';
  return 0;
}

Solution 2:

Suppose we are looking for the strongest friendship group where the cow with the minimum number of friends has exactly $d$ friends. We can find such a friendship group as follows: first, repeatedly remove any vertex with degree less than $d$ from the graph, and then return the largest connected component. We can do this in $O(M)$ time for each of $d=1,2,\dots$, and so on until the graph is empty. As a friendship group where every member has at least $d$ friends must contain at least $\frac{(d+1)d}{2}$ pairs of friendships, so once $\frac{(d+1)d}{2}>M$, the graph must be empty. Thus, this solution runs in $O(M\sqrt M)$ time.

The code solution uses DSU (which adds an extra factor of $\alpha(N)$), though this may be substituted with any other method of finding connected components (such as BFS or DFS).

Nick Wu's code:

#include <algorithm>
#include <cstdio>
#include <numeric>
#include <vector>
 
using namespace std;
 
struct disjoint_set {
  vector<int> p, sz;
  disjoint_set(int n) {
    p.assign(n, -1);
    sz.assign(n, 1);
  }
  int find(int x) {
    return p[x] < 0 ? x : (p[x] = find(p[x]));
  }
  int getsz(int x) {
    return sz[find(x)];
  }
  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return false;
    p[x] = y;
    sz[y] += sz[x];
    return true;
  }
};
 
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<vector<int>> edges(n);
  vector<int> edeg(n);
  for(int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--; b--;
    edeg[a]++;
    edeg[b]++;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  int ret = 0;
  vector<bool> deleted(n);
  vector<int> active(n);
  iota(active.begin(), active.end(), 0);
  for(int mindeg = 1; mindeg * mindeg <= m; mindeg++) {
    disjoint_set dsu(n);
    for(int i: active) {
      for(auto j: edges[i]) {
        if(!deleted[j] && dsu.merge(i, j)) ret = max(ret, dsu.getsz(i) * mindeg);
      }
    }
    vector<int> nactive;
    vector<int> q;
    for(int i: active) {
      if(edeg[i] == mindeg) {
        q.push_back(i);
      }
    }
    while(q.size()) {
      int i = q.back(); q.pop_back();
      if(deleted[i]) continue;
      deleted[i] = true;
      for(int j: edges[i]) {
        if(--edeg[j] <= mindeg) {
          q.push_back(j);
        }
      }
      edges[i].clear();
    }
    for(int i: active) if(edeg[i] > mindeg) nactive.push_back(i);
    active.swap(nactive);
  }
  printf("%d\n", ret);
}