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 }