Do the NP: find the largest clique
Mathematica, 34 bytes
Tr[1^#&@@FindClique[#<->#2&@@@#]]&
Basically FindClique does the job and "finds a largest clique in the graph g."
All the other stuff is converting input-list into graph
Input
[{{2, 5}, {2, 3}, {4, 17}, {1, 3}, {7, 13}, {5, 3}, {4, 3}, {4, 1}, {1, 5}, {5, 4}}]
Output
4
Input
[{{1296, 316}, {1650, 316}, {1296, 1650}, {1296, 52}, {1650, 711}, {711, 316}, {1650, 52}, {52, 711}, {1296, 711}, {52, 316}, {52, 1565}, {1565, 1296}, {1565, 316}, {1650, 1565}, {1296, 138}, {1565, 138}, {1565, 711}, {138, 1650}, {711, 138}, {138, 144}, {144, 1860}, {1296, 1860}, {1860, 52}, {711, 1639}}]
Output
6
thanx @Kelly Lowder for -10 bytes
Jelly, 20 bytes
ŒPẎ€µQL’=ċЀ`ẠµÐfṪQL
Try it online!
Of course this doesn't deserve the million :p
This would've beat Pyth, if not for the µ(...)µ
and 2-byte Ðf
.
Jelly, 15 18 16 bytes
+3 bytes to fix bugs in my method.
-2 bytes thanks to miles (noting that n×(n-1)÷2 = nC2)
ẎQL©c2⁼Lȧ®
ŒPÇ€Ṁ
A monadic link taking the list of friendships (edges) and returning an integer.
Try it online! forms the power-set of the edges in memory so is inefficient both in space and time (yep,that's O(2n) folks)!
How?
ẎQL©c2⁼Lȧ® - Link 1, isClique?: list, edges e.g. [[1,3],[2,3],[3,4],[4,1],[4,2],[2,1]]
Ẏ - tighten [ 1,3 , 2,3 , 3,4 , 4,1 , 4,2 , 2,1 ]
Q - de-duplicate (gets unique ids) [1,3,2,4]
L - length (get number of people involved) 4
© - (copy to the register)
c2 - combinations of 2 (z-choose-2) 6
L - length (of edges) 6
⁼ - equal? 1
® - recall value from register 4
ȧ - logical and 4
- (Note: the number of edges of a clique of size n is n*(n-1) and we're
- guaranteed no repeated edges and that all edges are two distinct ids)
ŒPÇ€Ṁ - Link: list of lists, edges
ŒP - power-set (all possible sets of edges (as lists))
Ç€ - call last link (1) as a monad for €ach
Ṁ - maximum