algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.cpp (2272B)


      1 #include <iostream>
      2 #include <unordered_map>
      3 #include <vector>
      4 #include <unordered_set>
      5 
      6 int dfs(std::unordered_map<int, std::vector<int>>& edges, std::unordered_set<int>& visited, int visiting, int parent, int& longest) {
      7 
      8     if(visited.contains(visiting)) {
      9         return -1;
     10     }
     11 
     12     visited.insert(visiting);
     13     auto& toFollow = edges[visiting];
     14     int bestDepth = 0;
     15     int secondDepth = 0;
     16 
     17     for(int i = 0; i < toFollow.size(); ++i) {
     18         if(toFollow[i] == parent) {
     19             continue;
     20         }
     21         int depthOf = dfs(edges, visited, toFollow[i], visiting, longest);
     22         if(depthOf == -1) {
     23             return -1; // cycle
     24         }
     25         if(depthOf > bestDepth) {
     26             secondDepth = bestDepth;
     27             bestDepth = depthOf;
     28         } else if(depthOf > secondDepth) {
     29             secondDepth = depthOf;
     30         }
     31     }
     32 
     33     if(bestDepth + secondDepth + 1 > longest) {
     34         longest = bestDepth + secondDepth + 1;
     35     }
     36     return bestDepth + 1; // inclusive
     37 }
     38 
     39 std::string solve(int vertices, std::unordered_map<int, std::vector<int>>& edges) {
     40 
     41     for(int i = 0; i < vertices; ++i) {
     42         if(edges[i].size() == 0) {
     43             return "Brain Melt";
     44         }
     45     }
     46 
     47     std::unordered_set<int> visited {};
     48     int components = 0;
     49 
     50     for(int i = 0; i < vertices; ++i) {
     51         if(!visited.contains(i)) {
     52             components += 1;
     53             if(components > 1) {
     54                 return "Many";
     55             }
     56             int longest = 0;
     57             int res = dfs(edges, visited, i, -1, longest);
     58             if(res == -1 || longest >= 4) {
     59                 return "Many";
     60             }
     61         }
     62     }
     63 
     64     return "2";
     65 }
     66 
     67 int main() {
     68 
     69     int testCases, numEdges, numVertices, c1,c2;
     70     std::cin >> testCases;
     71 
     72     for(int i = 0; i < testCases; ++i) {
     73         std::cin >> numVertices;
     74         std::cin >> numEdges;
     75 
     76         std::unordered_map<int, std::vector<int>> edges {};
     77     
     78         for(int x = 0; x < numEdges; ++x) {
     79             std::cin >> c1;
     80             std::cin >> c2;
     81             c1 -= 1;
     82             c2 -= 1; // make this zero indexed
     83             edges[c1].push_back(c2);
     84             edges[c2].push_back(c1);
     85         }
     86         std::cout << solve(numVertices,edges) << std::endl;
     87     }
     88 
     89     return 0;
     90 }