22
\$\begingroup\$

Background

At the time of writing this, the P vs NP problem is still unsolved, but you might have heard of Norbert Blum's new paper claiming proof that P != NP, which is already suspected to be erroneous (but we will see).

The problem discussed in this paper is the clique problem. At least that's what I read in a newspaper article, so correct me if I'm wrong, but in any case, I'd like you to write a program that solves the following variant:

The task

Assume we have a large school with lots of students. Each of these students has some friends at this school. A clique of students is a group consisting only of students who are friends with each other member.

Your program will receive pairs of students who are friends as its input. From this information, the program must find the size of the largest clique. Students are identified by integer IDs.

If you prefer mathematical terms, this means you're fed the edges of an undirected graph, identified by two nodes each.

Input

Your input will be a non-empty list of positive integer pairs, e.g. [[1,2],[2,5],[1,5]]. You can take this input in any sensible form, e.g. as an array of arrays, as lines of text containing two numbers each, etc ...

Output

The expected output is a single number n >= 2: the size of the largest clique. With the example input above, the result would be 3, as all students (1, 2 and 5) are friends with each other.

Test cases

[[1,2]]
=> 2

[[1,2],[3,1],[3,4]]
=> 2

[[1,2],[2,5],[1,5]]
=> 3

[[2,5],[2,3],[4,17],[1,3],[7,13],[5,3],[4,3],[4,1],[1,5],[5,4]]
=> 4 (the largest clique is [1,3,4,5])

[[15,1073],[23,764],[23,1073],[12,47],[47,15],[1073,764]]
=> 3 (the largest clique is [23,764,1073])

[[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]]
=> 6 (the largest clique is [52,316,711,1296,1565,1650])

You can use this (stupid) reference implementation (prints extra output with -d flag) for verifying the results of other test cases.

The rules

  1. Your program doesn't need a defined result on invalid input. So you can assume that:
    • you will always get at least one pair of IDs
    • each pair consists of two different IDs
    • no pair appears twice (swapping the places of the IDs would still be the same pair)
  2. Your algorithm isn't allowed to set an upper bound on input size. Purely technical limitations and limitations set by your language/environment (like stack size, computation time, etc) are of course inevitable.
  3. Standard loopholes are forbidden.
  4. This is , so the shortest code, measured in bytes, wins.
  5. If your algorithm has polynomial time complexity, you score -1 immediately regardless of your code size, but in that case, you might want to submit your solution somewhere else. ;)
\$\endgroup\$
  • 4
    \$\begingroup\$ I can almost guarantee that there will be someone who will do it (or try to), so it would simply be safer to remove it. If you want to reward people for doing it, you can offer a bounty to the shortest answer that does it it polynomial time. \$\endgroup\$ – caird coinheringaahing Aug 30 '17 at 11:55
  • 4
    \$\begingroup\$ @cairdcoinheringaahing if someone does it, the -1 is well deserved ;) \$\endgroup\$ – Felix Palmen Aug 30 '17 at 11:57
  • 13
    \$\begingroup\$ @cairdcoinheringaahing If somebody managed to prove that P = NP, them having the automatic lowest score on a code golf problem is the least of our concerns. That said, Rule 5 doesn't really contribute much to the challenge, so I agree that it should be removed. \$\endgroup\$ – Mego Aug 30 '17 at 12:17
  • 11
    \$\begingroup\$ @Mego it merely contributes a joke and a tiny bonus to the 1M offered by CMI. \$\endgroup\$ – Felix Palmen Aug 30 '17 at 12:19
  • 30
    \$\begingroup\$ Well, I won't, in favor of the few people having some sense of "scientific humor". Please don't comment more suggestions concerning this, thanks :) \$\endgroup\$ – Felix Palmen Aug 30 '17 at 12:21

13 Answers 13

6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Wow, explanation when you have time please \$\endgroup\$ – Mr. Xcoder Aug 30 '17 at 17:13
  • \$\begingroup\$ @EriktheOutgolfer I agree. I can probably add code to salvage... \$\endgroup\$ – Jonathan Allan Aug 30 '17 at 17:22
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – Erik the Outgolfer Aug 30 '17 at 17:23
  • \$\begingroup\$ 16 bytes \$\endgroup\$ – miles Aug 30 '17 at 23:05
  • \$\begingroup\$ @miles - nice, I just spent a while trying to get a 15 from that, I feel like it should be possible! \$\endgroup\$ – Jonathan Allan Aug 31 '17 at 0:22
13
\$\begingroup\$

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

\$\endgroup\$
  • 23
    \$\begingroup\$ Of course Mathematica has a builtin for this. \$\endgroup\$ – Erik the Outgolfer Aug 30 '17 at 13:06
  • 1
    \$\begingroup\$ Shave off 10 Bytes with Tr[1^#&@@FindClique[#<->#2&@@@#]]& \$\endgroup\$ – Kelly Lowder Aug 30 '17 at 13:30
  • 12
    \$\begingroup\$ FindClique ಠ___ಠ \$\endgroup\$ – Mr. Xcoder Aug 30 '17 at 13:43
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Amazing. I may as well give up now. \$\endgroup\$ – Mark Thomas Aug 30 '17 at 12:15
  • \$\begingroup\$ @FelixPalmen brute force :p \$\endgroup\$ – Erik the Outgolfer Aug 30 '17 at 12:16
  • \$\begingroup\$ @EriktheOutgolfer I didn't mean the runtime of the code ;) \$\endgroup\$ – Felix Palmen Aug 30 '17 at 12:18
  • \$\begingroup\$ @FelixPalmen I mean, brute force approach doesn't need much thinking :p \$\endgroup\$ – Erik the Outgolfer Aug 30 '17 at 12:19
  • \$\begingroup\$ Gives a MemoryError with the largest test-case :( Of course still valid, this is a "technical limitation" -- but just out of curiosity, is there a way to increase available resources with jelly? \$\endgroup\$ – Felix Palmen Aug 30 '17 at 13:24
3
\$\begingroup\$

J, 36 bytes

[:>./](#(]*[=2!])#@~.@,)@#~2#:@i.@^#

Try it online!

Runs in time O(2n) where n is the number of pairs.

A faster solution for 65 bytes is

3 :'$>{._2{~.@((+.&(e.&y)&<|.)@(-.,-.~)&>/#&,/:~@~.@,&.>/)~^:a:y'

Try it online!

Explanation

[:>./](#(]*[=2!])#@~.@,)@#~2#:@i.@^#  Input: list of pairs
                                   #  Length
                           2      ^   2^n
                               i.@    Range [0, 2^n)
                            #:@       Binary
                         #~           Copy
      (                )@             For each
                      ,                 Flatten
                   ~.@                  Unique
                 #@                     Length
        (       )                       Dyad with RHS at previous and LHS as next
               ]                          Get RHS
             2!                           Binomial coefficient, choose 2
            =                             Equals
           [                              Get LHS
          *                               Times
         ]                                Get RHS
       #                                Length
[:>./                                 Reduce using maximum
\$\endgroup\$
2
\$\begingroup\$

Pyth, 19 bytes

l{ef.AqLtl{T/LTTsMy

Try it here.

\$\endgroup\$
2
\$\begingroup\$

Python 2, 180 bytes

G=input()
m=0
L=len
for i in range(2**L(G)):
 u=[];p=sum([G[j]for j in range(L(G))if 2**j&i],u)
 for j in p:u+=[j][j in u:]
 m=max(m,L(u)*all(p.count(j)==L(u)-1for j in u))
print m

Try it online!

-2 thanks to shooqie.
-1 thanks to Mr. Xcoder.
-3 thanks to recursive.

\$\endgroup\$
  • \$\begingroup\$ You can save two bytes by assigning len to a variable \$\endgroup\$ – shooqie Aug 30 '17 at 15:46
  • \$\begingroup\$ 183 bytes. (x not in y) means 0**(x in y). \$\endgroup\$ – Mr. Xcoder Aug 30 '17 at 17:05
  • \$\begingroup\$ @Mr.Xcoder I knew there was a way to shorten it! Thanks! \$\endgroup\$ – Erik the Outgolfer Aug 30 '17 at 17:07
  • \$\begingroup\$ I have never used that before, just a trick that crossed thorugh my mind a couple of days ago but couldn't find a use to it yet. \$\endgroup\$ – Mr. Xcoder Aug 30 '17 at 17:08
  • \$\begingroup\$ @Mr.Xcoder Doesn't matter, if it works then why not? :D BTW you can also replace 0** with -~-. \$\endgroup\$ – Erik the Outgolfer Aug 30 '17 at 17:08
1
\$\begingroup\$

Pyth, 28 bytes

l{sSef<T.{SMQm.{ft{T.Cd2yS{s

Try it online

Explanation

l{sSef<T.{SMQm.{ft{T.Cd2yS{s
                         S{sQ  Get the distinct nodes in the (implicit) input.
                        y      Take every subset.
             m      .Cd2       Get the pairs...
                ft{T           ... without the [x, x] pairs...
              .{               ... as sets.
     f<T                        Choose the ones...
        .{  Q                   ... which are subsets of the input...
          SM                    ... with edges in sorted order.
    e                           Take the last element (largest clique).
l{sS                            Get the number of distinct nodes.
\$\endgroup\$
1
\$\begingroup\$

Python 3, 162 159 bytes

lambda x,f=lambda x:{i for s in x for i in s}:len(f(x))if all([(y,z)in x or(z,y)in x for y in f(x)for z in f(x)if y<z])else max(c(x.difference({y}))for y in x)

Try it online!

Function c takes vertices in the form of a set of sorted tuples ({(x,y),...} where x is less than y). A function called "entry" is in the TIO header to test with data in list of unsorted lists format. If clique, returns length. If not clique, returns max clique size of vertices, minus a vertice for each vertice in vertices. Exceeds time on last test case in TIO

Update: "or(z,y)in x" portion added to remove dependency on sortedness "f=lambda x:{i for s in x for i in s}" instead of itertools.chain wrapped in set.

-minus 3 bytes thanks to @Jonathan Allen

\$\endgroup\$
  • 1
    \$\begingroup\$ You may not assume the input edges are sorted. \$\endgroup\$ – Jonathan Allan Aug 30 '17 at 22:47
  • \$\begingroup\$ Aside - you do not need to name c, so can remove c= (you'd need to put c=\ at the end of the header and place the lambda at the top of the code block for TIO) \$\endgroup\$ – Jonathan Allan Aug 30 '17 at 22:49
  • \$\begingroup\$ Also you can get rid of s and replace s(...) with {*...} allowing the removal of some spaces too. \$\endgroup\$ – Jonathan Allan Aug 30 '17 at 22:56
  • 1
    \$\begingroup\$ @JonathanAllan thanks, sortedness fixed \$\endgroup\$ – Conner Johnston Aug 31 '17 at 2:38
1
\$\begingroup\$

05AB1E, 19 bytes

怘ʒDÙg<s{γ€gQP}θÙg

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Jelly, 28 bytes

œ^e³;U¤
Œcç/Ðfœ|Ṣ¥/€QµÐĿ-ịḢL

Try it online!

Faster solution that is able to solve the last test case in a second on TIO.

\$\endgroup\$
  • \$\begingroup\$ And what complexity does this have? If it's anything lower than O(2ⁿ) then it deserves $1,000,000. \$\endgroup\$ – Erik the Outgolfer Aug 31 '17 at 8:55
  • 1
    \$\begingroup\$ @EriktheOutgolfer, you are wrong, there are algorithms which have O(1.1888ⁿ) runtime. \$\endgroup\$ – rus9384 Aug 31 '17 at 10:15
  • \$\begingroup\$ Adding to that, to be worth a million, the n may only appear in the bases :) \$\endgroup\$ – Felix Palmen Aug 31 '17 at 11:13
  • \$\begingroup\$ @FelixPalmen, or it can' t. Anyway, for million one of two statements must be proved. \$\endgroup\$ – rus9384 Aug 31 '17 at 18:16
  • 1
    \$\begingroup\$ I believe this is O(1.414^n). You can see worse performance when the input is a complete graph. \$\endgroup\$ – miles Sep 1 '17 at 6:23
1
\$\begingroup\$

Java + Guava 23.0, 35 + 294 = 329 bytes

import com.google.common.collect.*;
a->{int l=0,o=1,c,z=a.size();for(;o>0&l<z;){o=0;c:for(Iterable<int[]>s:Sets.combinations(a,l*(l+1)/2)){Multiset<Integer>m=TreeMultiset.create();for(int[]x:s){m.add(x[0]);m.add(x[1]);}c=m.elementSet().size();for(int e:m.elementSet())if (m.count(e)!=c-1)continue c;l+=o=1;break;}}return z<3?2:l;}

This algorithm is not graphing, but instead is generating all combinations of pairs, of a specific size. I feed all pair-combinations into a multiset and check that they all have the expected size (the number of unique entries - 1). If they do, I found a clique and I go look for a bigger one.

From the Guava library, I use the new combinations method, and the tool-collection-type Multiset.

Ungolfed

import com.google.common.collect.*;
import java.util.function.*;

public class Main {

  public static void main(String[] args) {
    ToIntFunction<java.util.Set<int[]>> f
        = a -> {
          int l = 0, o = 1, c, z = a.size();
          for (; o > 0 & l < z;) {
            o = 0;
            c:
            for (Iterable<int[]> s : Sets.combinations(a, l * (l + 1) / 2)) {
              Multiset<Integer> m = TreeMultiset.create();
              for (int[] x : s) {
                m.add(x[0]);
                m.add(x[1]);
              }
              c = m.elementSet().size();
              for (int e : m.elementSet()) {
                if (m.count(e) != c - 1) {
                  continue c;
                }
              }
              l += o = 1;
              break;
            }
          }
          return z < 3 ? 2 : l;
        };
    int[][][] tests = {
      {{1, 2}},
      {{1, 2}, {3, 1}, {3, 4}},
      {{1, 2}, {2, 5}, {1, 5}},
      {{2, 5}, {2, 3}, {4, 17}, {1, 3}, {7, 13}, {5, 3}, {4, 3}, {4, 1}, {1, 5}, {5, 4}},
      {{15, 1073}, {23, 764}, {23, 1073}, {12, 47}, {47, 15}, {1073, 764}},
      {{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}}
    };
    for (int[][] test : tests) {
      java.util.Set<int[]> s = new java.util.HashSet<int[]>();
      for (int[] t : test) {
        s.add(t);
      }
      System.out.println(f.applyAsInt(s));
    }
  }
}
\$\endgroup\$
  • \$\begingroup\$ I'd be very surprised, see Finding maximum cliques in arbitrary graphs -- but it'll take me a while to analyze this code, I'm not too familiar with Java :) \$\endgroup\$ – Felix Palmen Aug 31 '17 at 10:20
  • \$\begingroup\$ @FelixPalmen I liked this challenge so my answer will stay no matter what, but I'm totally okay with removing the "-1" if it's not a polynomial complexity. Then I should probably go review some books :P \$\endgroup\$ – Olivier Grégoire Aug 31 '17 at 10:24
  • \$\begingroup\$ "Combination of size x is polynomial" <- are you sure? I guess that's the method used. The return value is an AbstractSet with an iterator, and the following for loop will call this iterator x! times if I'm not mistaken... \$\endgroup\$ – Felix Palmen Aug 31 '17 at 11:11
  • \$\begingroup\$ Correction: as long as x < n (with n being the complete size of the input set), it's n!/(x!(n-x)!), still not polynomial :) \$\endgroup\$ – Felix Palmen Aug 31 '17 at 11:18
  • \$\begingroup\$ @FelixPalmen You're most likely right. Also, are you saying that if I make a combinations method that's X^n (which is entirely possible), I can get it? Meanwhile, I remove my claim of the "-1". \$\endgroup\$ – Olivier Grégoire Aug 31 '17 at 11:21
1
\$\begingroup\$

Python 2, 102 bytes

def f(g):
 x=g
 while x:y=x;x=map(set,{tuple(u|v)for u in x for v in x if u^v in g})
 return len(y[0])

Try it online!

\$\endgroup\$
0
\$\begingroup\$

6502 machine code (C64), 774 703 bytes

(I just had to do this, my C64 can do everything ... hehe)

hexdump:

00 C0 A9 00 A2 08 9D 08 00 CA 10 FA A2 04 9D FB 00 CA 10 FA 20 54 C0 B0 20 AD 
C9 C2 AE CA C2 20 92 C1 B0 31 8D 31 C0 AD CB C2 AE CC C2 20 92 C1 B0 23 A2 FF 
20 FE C1 90 DB 20 6A C2 20 C1 C1 B0 05 20 6A C2 50 F6 A5 FB 8D D3 C2 20 43 C1 
A9 CD A0 C2 20 1E AB 60 A2 00 86 CC 8E 61 C0 20 E4 FF F0 FB A2 FF C9 0D F0 10 
E0 0B 10 0C 9D BD C2 20 D2 FF E8 8E 61 C0 D0 E5 C6 CC A9 20 20 D2 FF A9 0D 20 
D2 FF A9 00 9D BD C2 AA BD BD C2 F0 5C C9 30 30 0E C9 3A 10 0A 9D CD C2 E8 E0 
06 F0 4C D0 E9 C9 20 D0 46 A9 00 9D CD C2 E8 8E BC C0 20 EB C0 AD D3 C2 8D C9 
C2 AD D4 C2 8D CA C2 A2 FF A0 00 BD BD C2 F0 0F C9 30 30 21 C9 3A 10 1D 99 CD 
C2 C8 E8 D0 EC A9 00 99 CD C2 20 EB C0 AD D3 C2 8D CB C2 AD D4 C2 8D CC C2 18 
60 38 60 A2 FF E8 BD CD C2 D0 FA A0 06 88 CA 30 0A BD CD C2 29 0F 99 CD C2 10 
F2 A9 00 99 CD C2 88 10 F8 A9 00 8D D3 C2 8D D4 C2 A2 10 A0 7B 18 B9 53 C2 90 
02 09 10 4A 99 53 C2 C8 10 F2 6E D4 C2 6E D3 C2 CA D0 01 60 A0 04 B9 CE C2 C9 
08 30 05 E9 03 99 CE C2 88 10 F1 30 D2 A2 06 A9 00 9D CC C2 CA D0 FA A2 08 A0 
04 B9 CE C2 C9 05 30 05 69 02 99 CE C2 88 10 F1 A0 04 0E D3 C2 B9 CE C2 2A C9 
10 29 0F 99 CE C2 88 10 F2 CA D0 D9 C8 B9 CD C2 F0 FA 09 30 9D CD C2 E8 C8 C0 
06 F0 05 B9 CD C2 90 F0 A9 00 9D CD C2 60 85 0A A4 09 C0 00 F0 11 88 B9 D5 C2 
C5 0A D0 F4 8A D9 D5 C3 D0 EE 98 18 60 A4 09 E6 09 D0 01 60 A5 0A 99 D5 C2 8A 
99 D5 C3 98 99 D5 C4 18 60 A6 0B E4 09 30 01 60 BD D5 C5 C5 0B 30 09 A9 00 9D 
D5 C5 E6 0B D0 E9 A8 FE D5 C5 8A 29 01 D0 02 A0 00 BD D5 C4 59 D5 C4 9D D5 C4 
59 D5 C4 99 D5 C4 5D D5 C4 9D D5 C4 A9 00 85 0B 18 60 A8 A5 0C D0 08 A9 20 C5 
0D F0 21 A5 0C 8D 1E C2 8D 21 C2 A5 0D 09 60 8D 1F C2 49 E0 8D 22 C2 8C FF FF 
8E FF FF E6 0C D0 02 E6 0D 18 60 86 0E 84 0F A5 0D 09 60 8D 54 C2 49 E0 8D 5F 
C2 A6 0C CA E0 FF D0 10 AC 54 C2 88 C0 60 10 02 18 60 8C 54 C2 CE 5F C2 BD 00 
FF C5 0E F0 04 C5 0F D0 E0 BD 00 FF C5 0E F0 04 C5 0F D0 D5 38 60 A2 00 86 FC 
86 FD 86 FE BD D5 C4 A8 A6 FE E4 FC 10 11 BD D5 C7 AA 20 2B C2 90 14 E6 FE A6 
FE E4 FC D0 EF A6 FD BD D5 C4 A6 FC E6 FC 9D D5 C7 E6 FD A6 FD E4 09 D0 16 A6 
FB E4 FC 10 0F A2 00 BD D5 C7 9D D5 C6 E8 E4 FC D0 F5 86 FB 60 A0 00 84 FE F0 
B5

Online demo

Usage: Start with sys49152, then enter the pairs one per line like e.g.

15 1073
23 764
23 1073
12 47
47 15
1073 764

Backsapce isn't handled during input (but if you use vice, just copy&paste your input into the emulator). Enter an empty line to start calculation.

This is too large to post an explanatory disassembly listing here, but you can browse the ca65-style assembly source. The algorithm is very inefficient, it generates every possible permutation of the nodes and with each of these greedily builds a clique by checking all the edges. This allows for a space efficiency of O(n) (kind of important on a machine with this little RAM), but has horrible runtime efficiency (*). The theoretical limits are up to 256 nodes and up to 8192 edges.

  • -71 bytes: optimized routine for checking edges and zeropage usage

There's a larger (883 805 bytes) version with better features:

  • visual feedback during calculation (each permutation of the nodes changes the border color)
  • uses bank switching to store the edges in the RAM "hidden" by the ROMs to conserve space
  • outputs the size and the nodes of the maximal clique found

Online demo

Browse source


(*) The last test case takes something between 12 and 20 hours (I was sleeping when it finally finished). The other test cases finish at worst within some minutes.

Screenshot of last test case

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.