(Analysis by Benjamin Qi)

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);
}