Branch data     Line data    Source code

       1                 :             : #include <algorithm>
       2                 :             : #include <fstream>
       3                 :             : #include <iostream>
       4                 :             : #include <ranges>
       5                 :             : #include <string>
       6                 :             : #include <unordered_map>
       7                 :             : #include <unordered_set>
       8                 :             : #include <vector>
       9                 :             : 
      10                 :             : using namespace std;
      11                 :             : 
      12                 :             : vector<unordered_set<int>> connections;
      13                 :             : unordered_set<int> largestClique;
      14                 :             : 
      15                 :        1541 : void findLargestClique(const unordered_set<int>& R, unordered_set<int>& P, unordered_set<int>& X) {
      16   [ +  +  +  +  :        1541 :   if (P.empty() && X.empty() && R.size() > largestClique.size()) {
             +  +  +  + ]
      17                 :           2 :     largestClique = R;
      18                 :        1434 :     return;
      19                 :             :   }
      20         [ +  + ]:        1539 :   if (R.size() + P.size() <= largestClique.size()) {
      21                 :        1432 :     return;
      22                 :             :   }
      23                 :             : 
      24                 :         107 :   unordered_set<int> P_copy = P;
      25         [ +  + ]:        1647 :   for (int v : P_copy) {
      26                 :        1540 :     unordered_set<int> R_new = R;
      27                 :        1540 :     unordered_set<int> P_new;
      28                 :        1540 :     unordered_set<int> X_new;
      29                 :        1540 :     R_new.insert(v);
      30                 :             : 
      31         [ +  + ]:      142985 :     for (int p : P) {
      32         [ +  + ]:      141445 :       if (connections[v].contains(p)) {
      33                 :        7742 :         P_new.insert(p);
      34                 :             :       }
      35                 :             :     }
      36         [ +  + ]:      141505 :     for (int x : X) {
      37         [ +  + ]:      139965 :       if (connections[v].contains(x)) {
      38                 :        7783 :         X_new.insert(x);
      39                 :             :       }
      40                 :             :     }
      41                 :             : 
      42                 :        1540 :     findLargestClique(R_new, P_new, X_new);
      43                 :             : 
      44                 :        1540 :     P.erase(v);
      45                 :        1540 :     X.insert(v);
      46                 :        1540 :   }
      47                 :         107 : }
      48                 :             : 
      49                 :           2 : int main() {
      50                 :           2 :   ifstream input{"input.txt"};
      51         [ +  + ]:           2 :   if (!input) {
      52                 :           1 :     cerr << "Error: Could not open input file.\n";
      53                 :           1 :     return 1;
      54                 :             :   }
      55                 :             : 
      56                 :           1 :   unordered_map<string,int> id;
      57                 :           1 :   vector<string> name;
      58                 :             : 
      59                 :        6760 :   auto getId = [&id, &name](const string& s) {
      60                 :        6760 :     auto [it, added] = id.try_emplace(s, (int)id.size());
      61         [ +  + ]:        6760 :     if (added) name.push_back(s);
      62                 :        6760 :     return it->second;
      63                 :           1 :   };
      64                 :             : 
      65                 :           1 :   vector<pair<int,int>> edges;
      66                 :           1 :   string a;
      67                 :           1 :   string b;
      68   [ +  +  +  -  :        3381 :   while (getline(input, a, '-') && getline(input, b)) {
                   +  + ]
      69                 :        3380 :     int u = getId(a);
      70                 :        3380 :     int v = getId(b);
      71         [ +  - ]:        3380 :     if (u != v) edges.emplace_back(u, v);
      72                 :             :   }
      73                 :             : 
      74                 :           1 :   int n = (int)name.size();
      75                 :           1 :   connections.assign(n, {});
      76         [ +  + ]:        3381 :   for (auto [u, v] : edges) {
      77                 :        3380 :     connections[u].insert(v);
      78                 :        3380 :     connections[v].insert(u);
      79                 :             :   }
      80                 :             : 
      81                 :           1 :   unordered_set<int> R;
      82                 :           1 :   unordered_set<int> P;
      83                 :           1 :   unordered_set<int> X;
      84         [ +  + ]:         521 :   for (int i = 0; i < n; ++i) {
      85                 :         520 :     P.insert(i);
      86                 :             :   }
      87                 :           1 :   findLargestClique(R, P, X);
      88                 :             : 
      89                 :           1 :   vector<string> result;
      90         [ +  + ]:          14 :   for (int v : largestClique) {
      91                 :          13 :     result.push_back(name[v]);
      92                 :             :   }
      93                 :           1 :   std::ranges::sort(result);
      94                 :             : 
      95                 :           1 :   std::cout << std::ranges::to<std::string>(result | std::views::join_with(',')) << std::endl;
      96         [ +  + ]:           3 : }