#include <iostream> #include <vector> #include <stack> #include <unordered_set> #include <set> #include <algorithm> using namespace std; void getConnectedComponents(const vector<vector<int>> &graph, const unordered_set<int> &goodCities, vector<vector<int>> &components) { vector<bool> visited(graph.size(), false); int currComponent = 0; for(int i=0; i<graph.size(); i++) { if((visited[i]) || (goodCities.count(i) == 0)) continue; stack<int> toDo; toDo.push(i); visited[i] = true; components.push_back(vector<int>{}); while(!toDo.empty()) { int curr = toDo.top(); toDo.pop(); components.back().push_back(curr); for(auto it = graph[curr].cbegin(); it != graph[curr].cend(); ++it) { if((visited[*it]) || (goodCities.count(*it) == 0)) continue; toDo.push(*it); visited[*it] = true; } } } } struct city { int idx; int degree; city(int i, int d): idx(i), degree(d) {}; bool operator<(const city &c) const noexcept { if(degree == c.degree) return idx < c.idx; return degree < c.degree; } }; int main() { ios_base::sync_with_stdio(false); vector<vector<int>> graph; vector<vector<int>> connectedComponents; vector<int> degrees; set<city> cityQueue; unordered_set<int> goodCities; int N, M, d; cin >> N; cin >> M; cin >> d; graph.resize(N); int a, b; for(int i=0; i<M; i++) { cin >> a; cin >> b; graph[a-1].push_back(b-1); graph[b-1].push_back(a-1); } for(int i=0; i<graph.size(); i++) { degrees.push_back(graph[i].size()); cityQueue.insert(city(i, graph[i].size())); } while((!cityQueue.empty()) && (cityQueue.begin()->degree < d)) { int currIdx = cityQueue.begin()->idx; cityQueue.erase(cityQueue.begin()); degrees[currIdx] = 0; for(int i=0; i<graph[currIdx].size(); i++) { if(degrees[graph[currIdx][i]] == 0) continue; auto it = cityQueue.find(city(graph[currIdx][i], degrees[graph[currIdx][i]])); cityQueue.erase(it); degrees[graph[currIdx][i]]--; cityQueue.insert(city(graph[currIdx][i], degrees[graph[currIdx][i]])); } } for(auto it = cityQueue.cbegin(); it != cityQueue.cend(); ++it) { goodCities.insert(it->idx); } if(goodCities.empty()) { cout << "NIE" << endl; return 0; } getConnectedComponents(graph, goodCities, connectedComponents); int maxIdx, maxCount = 0;; for(int i=0; i<connectedComponents.size(); i++) { if(maxCount < connectedComponents[i].size()) { maxCount = connectedComponents[i].size(); maxIdx = i; } } sort(connectedComponents[maxIdx].begin(), connectedComponents[maxIdx].end()); cout << maxCount << endl; for(auto a : connectedComponents[maxIdx]) cout << a+1 << " "; cout << endl; 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 | #include <iostream> #include <vector> #include <stack> #include <unordered_set> #include <set> #include <algorithm> using namespace std; void getConnectedComponents(const vector<vector<int>> &graph, const unordered_set<int> &goodCities, vector<vector<int>> &components) { vector<bool> visited(graph.size(), false); int currComponent = 0; for(int i=0; i<graph.size(); i++) { if((visited[i]) || (goodCities.count(i) == 0)) continue; stack<int> toDo; toDo.push(i); visited[i] = true; components.push_back(vector<int>{}); while(!toDo.empty()) { int curr = toDo.top(); toDo.pop(); components.back().push_back(curr); for(auto it = graph[curr].cbegin(); it != graph[curr].cend(); ++it) { if((visited[*it]) || (goodCities.count(*it) == 0)) continue; toDo.push(*it); visited[*it] = true; } } } } struct city { int idx; int degree; city(int i, int d): idx(i), degree(d) {}; bool operator<(const city &c) const noexcept { if(degree == c.degree) return idx < c.idx; return degree < c.degree; } }; int main() { ios_base::sync_with_stdio(false); vector<vector<int>> graph; vector<vector<int>> connectedComponents; vector<int> degrees; set<city> cityQueue; unordered_set<int> goodCities; int N, M, d; cin >> N; cin >> M; cin >> d; graph.resize(N); int a, b; for(int i=0; i<M; i++) { cin >> a; cin >> b; graph[a-1].push_back(b-1); graph[b-1].push_back(a-1); } for(int i=0; i<graph.size(); i++) { degrees.push_back(graph[i].size()); cityQueue.insert(city(i, graph[i].size())); } while((!cityQueue.empty()) && (cityQueue.begin()->degree < d)) { int currIdx = cityQueue.begin()->idx; cityQueue.erase(cityQueue.begin()); degrees[currIdx] = 0; for(int i=0; i<graph[currIdx].size(); i++) { if(degrees[graph[currIdx][i]] == 0) continue; auto it = cityQueue.find(city(graph[currIdx][i], degrees[graph[currIdx][i]])); cityQueue.erase(it); degrees[graph[currIdx][i]]--; cityQueue.insert(city(graph[currIdx][i], degrees[graph[currIdx][i]])); } } for(auto it = cityQueue.cbegin(); it != cityQueue.cend(); ++it) { goodCities.insert(it->idx); } if(goodCities.empty()) { cout << "NIE" << endl; return 0; } getConnectedComponents(graph, goodCities, connectedComponents); int maxIdx, maxCount = 0;; for(int i=0; i<connectedComponents.size(); i++) { if(maxCount < connectedComponents[i].size()) { maxCount = connectedComponents[i].size(); maxIdx = i; } } sort(connectedComponents[maxIdx].begin(), connectedComponents[maxIdx].end()); cout << maxCount << endl; for(auto a : connectedComponents[maxIdx]) cout << a+1 << " "; cout << endl; return 0; } |