#include <stdio.h> #include <set> #include <vector> #include <algorithm> int anyFromSet(std::set<int> &theSet) { int anyValue = *theSet.begin(); theSet.erase(anyValue); return anyValue; } bool contains(std::set<int> &theSet, int value) { return theSet.find(value) != theSet.end(); } std::vector<int> getAnyConnectedComponent(std::vector<std::set<int>> &nodes, std::set<int> &unvisitedNodes) { std::set<int> nodesToCheck; std::vector<int> connectedComponent; int firstNode = anyFromSet(unvisitedNodes); connectedComponent.push_back(firstNode); for(auto node : nodes[firstNode]) { nodesToCheck.insert(node); unvisitedNodes.erase(node); connectedComponent.push_back(node); } while (!nodesToCheck.empty()){ int currentCheckedNode = anyFromSet(nodesToCheck); for(auto node : nodes[currentCheckedNode]) { if(contains(unvisitedNodes, node)){ nodesToCheck.insert(node); unvisitedNodes.erase(node); connectedComponent.push_back(node); } } } return connectedComponent; } void connectedComponents(std::vector<std::set<int>> &nodes) { std::set<int> nodesToCheck; for(int node = 1 ; node < nodes.size() ; ++node) { if(nodes[node].size() > 0) { nodesToCheck.insert(node); } } std::vector<int> longest; while(!nodesToCheck.empty()) { std::vector<int> component = getAnyConnectedComponent(nodes, nodesToCheck); if(component.size() > longest.size()) { longest = component; } } std::sort(longest.begin(), longest.end()); printf("%d\n", longest.size()); for(auto node: longest) { printf("%d ", node); } } int main() { int n, m, d; scanf("%d %d %d", &n, &m, &d); std::vector<std::set<int>> nodes(n+1); for(int i = 0 ; i < m ; ++i) { int first, second; scanf("%d %d", &first, &second); nodes[first].insert(second); nodes[second].insert(first); } std::set<int> nodesToCheck; for(int i = 1 ; i <= n ; ++i) { if(nodes[i].size() < d) { nodesToCheck.insert(i); } } while(!nodesToCheck.empty()) { int nodeToCheck = *nodesToCheck.begin(); for(auto vertex : nodes[nodeToCheck]) { nodes[vertex].erase(nodeToCheck); if(nodes[vertex].size() < d) { nodesToCheck.insert(vertex); } } nodes[nodeToCheck].clear(); nodesToCheck.erase(nodeToCheck); } bool found = false; for(int i = 1 ; i <= n ; ++i) { if(nodes[i].size() >= d) { found = true; } } if(!found) { printf("NIE\n"); return 0; } connectedComponents(nodes); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 | #include <stdio.h> #include <set> #include <vector> #include <algorithm> int anyFromSet(std::set<int> &theSet) { int anyValue = *theSet.begin(); theSet.erase(anyValue); return anyValue; } bool contains(std::set<int> &theSet, int value) { return theSet.find(value) != theSet.end(); } std::vector<int> getAnyConnectedComponent(std::vector<std::set<int>> &nodes, std::set<int> &unvisitedNodes) { std::set<int> nodesToCheck; std::vector<int> connectedComponent; int firstNode = anyFromSet(unvisitedNodes); connectedComponent.push_back(firstNode); for(auto node : nodes[firstNode]) { nodesToCheck.insert(node); unvisitedNodes.erase(node); connectedComponent.push_back(node); } while (!nodesToCheck.empty()){ int currentCheckedNode = anyFromSet(nodesToCheck); for(auto node : nodes[currentCheckedNode]) { if(contains(unvisitedNodes, node)){ nodesToCheck.insert(node); unvisitedNodes.erase(node); connectedComponent.push_back(node); } } } return connectedComponent; } void connectedComponents(std::vector<std::set<int>> &nodes) { std::set<int> nodesToCheck; for(int node = 1 ; node < nodes.size() ; ++node) { if(nodes[node].size() > 0) { nodesToCheck.insert(node); } } std::vector<int> longest; while(!nodesToCheck.empty()) { std::vector<int> component = getAnyConnectedComponent(nodes, nodesToCheck); if(component.size() > longest.size()) { longest = component; } } std::sort(longest.begin(), longest.end()); printf("%d\n", longest.size()); for(auto node: longest) { printf("%d ", node); } } int main() { int n, m, d; scanf("%d %d %d", &n, &m, &d); std::vector<std::set<int>> nodes(n+1); for(int i = 0 ; i < m ; ++i) { int first, second; scanf("%d %d", &first, &second); nodes[first].insert(second); nodes[second].insert(first); } std::set<int> nodesToCheck; for(int i = 1 ; i <= n ; ++i) { if(nodes[i].size() < d) { nodesToCheck.insert(i); } } while(!nodesToCheck.empty()) { int nodeToCheck = *nodesToCheck.begin(); for(auto vertex : nodes[nodeToCheck]) { nodes[vertex].erase(nodeToCheck); if(nodes[vertex].size() < d) { nodesToCheck.insert(vertex); } } nodes[nodeToCheck].clear(); nodesToCheck.erase(nodeToCheck); } bool found = false; for(int i = 1 ; i <= n ; ++i) { if(nodes[i].size() >= d) { found = true; } } if(!found) { printf("NIE\n"); return 0; } connectedComponents(nodes); return 0; } |