CliqueCount
SRM 256 · 2005-08-02 · by lars2520
SRM 256 · 2005-08-02 · by lars2520 · Brute Force, Graph Theory
Problem Statement
Problem Statement
An undirected graph is defined as a set of vertices with undirected edges connecting some of the pairs of vertices. A clique in an undirected graph is a non-empty subset of vertices where there is a direct connection between every pair of vertices in the subset. A maximal clique is a clique that is not a proper subset of any other clique. You will be given a graph as a String[] where the jth character of the ith element is a '1' if and only if vertices i and j are connected. Your method should return the number of maximal cliques in the graph.
Constraints
- graph will contain between 1 and 20 elements, inclusive.
- Each element of graph will contain as many characters as graph has elements.
- Each character in graph will be '0' or '1'.
- Character j of element i of graph will be the same as character i of element j for all i and j.
- Character i of element i of graph will be '0' for all i.
Examples
0)
{"010",
"100",
"000"}
Returns: 2
If the vertices are 0, 1, and 2, corresonding to the elements of the input, then the two maximal cliques are {0,1} and {2}.
1)
{"011",
"101",
"110"}
Returns: 1
All nodes are connected so there is just one big clique.
2)
{"00010000000000100000",
"00110000000000000000",
"01011001000000011000",
"11101000000100010110",
"00110000001100000000",
"00000000010000000001",
"00000000000000011001",
"00100000000010000001",
"00000000000100011000",
"00000100000010000010",
"00001000000000000010",
"00011000100001000101",
"00000001010000000000",
"00000000000100000010",
"10000000000000000010",
"00110010100000000000",
"00100010100000000000",
"00010000000100000000",
"00010000011001100000",
"00000111000100000000"}
Returns: 28
3)
{"00",
"00"}
Returns: 2
4)
{"01111111111111111111",
"10111111111111111111",
"11011111111111111111",
"11101111111111111111",
"11110111111111111111",
"11111011111111111111",
"11111101111111111111",
"11111110111111111111",
"11111111011111111111",
"11111111101111111111",
"11111111110111111111",
"11111111111011111111",
"11111111111101111111",
"11111111111110111111",
"11111111111111011111",
"11111111111111101111",
"11111111111111110111",
"11111111111111111011",
"11111111111111111101",
"11111111111111111110"}
Returns: 1
Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CliqueCount with a public method int countCliques(vector<string> graph) · 69 test cases · 2 s / 256 MB per case