day23b.cpp (1404B)
1 #include <algorithm> 2 #include <cstdint> 3 #include <iostream> 4 #include <map> 5 #include <queue> 6 #include <ranges> 7 #include <set> 8 #include <sstream> 9 #include <string> 10 #include <string_view> 11 #include <vector> 12 using namespace std; 13 14 set<int> computers; 15 bool m[26*26][26*26]; 16 17 int index(char a, char b) { return (int)(b-'a') + 26*(int)(a-'a'); } 18 void printnode(int i) { cout << (char)('a'+i/26) << (char)('a'+i%26); } 19 bool t(int i) { return i % 26 == 't' - 'a'; } 20 21 bool all(int i, const set<int>& v) { 22 for (auto j : v) 23 if (!m[i][j]) 24 return false; 25 return true; 26 } 27 28 int main() { 29 string line; 30 while (getline(cin, line)) { 31 int i = index(line[0], line[1]); 32 int j = index(line[3], line[4]); 33 computers.insert(i); 34 computers.insert(j); 35 m[i][j] = m[j][i] = true; 36 } 37 38 vector<set<int>> cliques[15]; 39 cliques[0].push_back(set<int>()); 40 for (int i = 1; ; i++) { 41 for (auto& c : cliques[i-1]) { 42 int mm = *max_element(c.begin(), c.end()); 43 for (auto j : computers) { 44 if (j <= mm) continue; 45 if (all(j, c)) { 46 set nw = c; 47 nw.insert(j); 48 cliques[i].push_back(nw); 49 } 50 } 51 } 52 auto n = cliques[i].size(); 53 cout << "Found " << n << " cliques of size " << i << endl; 54 if (n == 0) break; 55 auto cc = *cliques[i].begin(); 56 vector<int> cv(cc.begin(), cc.end()); 57 sort(cv.begin(), cv.end()); 58 for (auto j : cv) { 59 printnode(j); 60 cout << ","; 61 } 62 cout << endl; 63 } 64 65 return 0; 66 }