Clique

A bunch of people on Facebook would like to find out the largest clique among them.
(Maybe this will be the next facebook application?)

A clique is defined as a group of people where everyone is friends with everyone else.
Given a list of friends (friendship works both ways), your job is to output the size of this clique.
For the sake of privacy (and your convenience), we have replaced the names of the people with numbers.

Input

Number of people, 1 ≤ N ≤ 32
Number of friendships, 1 ≤ M ≤ N*(N-1)/2
M lines, each with 2 numbers 1 ≤ a, b ≤ N meaning that a and b are friends.
There will be no duplicate edges.

NOTE: 50% of test cases will have N ≤ 24.

Output

The size of the maximum clique.

Sample Input

6 7
2 3
2 4
2 5
3 4
3 5
4 5
5 6

Sample Output

4

Friends 2,3,4,5 form the largest clique.

All Submissions
Best Solutions


Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: Sep 24, 2008
Author: hansonw1

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I keep on getting RE (status =1) for test case 3. Is there anyway I can see what the error is? It gives me the text clipped so, I can't see what the issue is. My program works for everything else.

In general, don't expect for us to tell you. You should be figuring this out yourself!

But... I'm feeling nice today.
 
Traceback (most recent call last):
File "a.out", line 36, in <module>
print max(cnts)
ValueError: max() arg is an empty sequence

Ok thanks, I fixed it now. Also, what is the reason for clipping the output in the first place?

To avoid silly stuff like
puts $_ while gets

Test case 0 says that I got AC on the case, but says 0/0

Test 0 is identical to sample input.

There are only 2N combinations of cliques - you can try all of them. (this will give you partial points)
You can optimize this, though.

The approach to generate these combinations is quite similar to COCI08 #2 - Perket.