D1 - Friends

最大クリーク問題は一般にNP困難ですが、本問題では「各頂点の次数は $3$ 以下」という制約があるので、うまく多項式時間で解くことが出来ます。

頂点 $i$ を含んだ完全グラフの頂点の候補は、その頂点とそれに隣接した頂点の最大 $4$ つです。
また、頂点 $i$ を必ず含むので、それを除いた $3$ つの取捨選択をbit全探索を用いて試せばよいです。
以上より、計算量は$O(N)$です。

類題

ABC02 D - 派閥

n, m = map(int,input().split())

G = [[]for _ in range(n)]
E = set()
for i in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    E.add((a,b))
    E.add((b,a))

ans = 0
for i in range(n):
    l = len(G[i])
    for j in range(1<<l):
        A = [i]
        for k in range(l):
            if(j>>k & 1):
                A.append(G[i][k])

        bl = True
        for a in range(len(A)):
            for b in range(a+1, len(A)):
                if((A[a],A[b]) not in E and (A[b],A[a]) not in E):
                    bl = False
        if(bl):
            ans = max(ans,len(A))

print(ans)

#include<bits/stdc++.h>
using namespace std;

int main() {

    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    int ans = 2;
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int to : graph[i]) {
            for (int find : graph[i]) {
                cnt += count(graph[to].begin(), graph[to].end(), find);
            }
        }
        if(cnt > 0) ans = max(ans, 3);
        if(cnt == 6) ans = max(ans, 4);
    }

    cout << ans << endl;
}