#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; int main() { uint32_t n, m, a, b, d; ios_base::sync_with_stdio(0); cin>>n>>m>>d; vector<vector<uint32_t>> g(n+1); vector<bool> removed(n+1); vector<uint32_t> deg(n+1); for(uint32_t i = 0; i < m; ++i) { cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } queue<uint32_t> q; for(int i = 1; i <= n; ++i) { deg[i] = g[i].size(); if(deg[i] < d) { q.push(i); removed[i] = true; } else removed[i] = false; } while(!q.empty()) { uint32_t i = q.front(); q.pop(); for(uint32_t j = 0; j < g[i].size(); ++j) if(!removed[g[i][j]]) { deg[g[i][j]]--; if(deg[g[i][j]] < d) { q.push(g[i][j]); removed[g[i][j]] = true; } } } vector<bool> visited(n+1, false); uint32_t max = 0, index = 0, cur = 0; //q jest juz puste for(uint32_t i = 1; i <= n; ++i) { if(!visited[i] && !removed[i]) { cur = 0; visited[i] = true; q.push(i); while(!q.empty()) { uint32_t i = q.front(); q.pop(); ++cur; for(uint32_t j = 0; j < g[i].size(); ++j) if(!visited[g[i][j]] && !removed[g[i][j]]) { q.push(g[i][j]); visited[g[i][j]] = true; } } if(cur > max) { max = cur; index = i; } } } if(cur == 0) cout<<"NIE"; else { //visited teraz ma odwrotne znaczenie -> true = nieodwiedzony cout<<max<<endl; vector<uint32_t> ans; visited[index] = false; q.push(index); while(!q.empty()) { uint32_t i = q.front(); q.pop(); ans.push_back(i); for(uint32_t j = 0; j < g[i].size(); ++j) if(visited[g[i][j]] && !removed[g[i][j]]) { q.push(g[i][j]); visited[g[i][j]] = false; } } sort(ans.begin(), ans.end()); for(uint32_t i = 0; i < ans.size(); ++i) cout<<ans[i]<<" "; } 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 | #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; int main() { uint32_t n, m, a, b, d; ios_base::sync_with_stdio(0); cin>>n>>m>>d; vector<vector<uint32_t>> g(n+1); vector<bool> removed(n+1); vector<uint32_t> deg(n+1); for(uint32_t i = 0; i < m; ++i) { cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } queue<uint32_t> q; for(int i = 1; i <= n; ++i) { deg[i] = g[i].size(); if(deg[i] < d) { q.push(i); removed[i] = true; } else removed[i] = false; } while(!q.empty()) { uint32_t i = q.front(); q.pop(); for(uint32_t j = 0; j < g[i].size(); ++j) if(!removed[g[i][j]]) { deg[g[i][j]]--; if(deg[g[i][j]] < d) { q.push(g[i][j]); removed[g[i][j]] = true; } } } vector<bool> visited(n+1, false); uint32_t max = 0, index = 0, cur = 0; //q jest juz puste for(uint32_t i = 1; i <= n; ++i) { if(!visited[i] && !removed[i]) { cur = 0; visited[i] = true; q.push(i); while(!q.empty()) { uint32_t i = q.front(); q.pop(); ++cur; for(uint32_t j = 0; j < g[i].size(); ++j) if(!visited[g[i][j]] && !removed[g[i][j]]) { q.push(g[i][j]); visited[g[i][j]] = true; } } if(cur > max) { max = cur; index = i; } } } if(cur == 0) cout<<"NIE"; else { //visited teraz ma odwrotne znaczenie -> true = nieodwiedzony cout<<max<<endl; vector<uint32_t> ans; visited[index] = false; q.push(index); while(!q.empty()) { uint32_t i = q.front(); q.pop(); ans.push_back(i); for(uint32_t j = 0; j < g[i].size(); ++j) if(visited[g[i][j]] && !removed[g[i][j]]) { q.push(g[i][j]); visited[g[i][j]] = false; } } sort(ans.begin(), ans.end()); for(uint32_t i = 0; i < ans.size(); ++i) cout<<ans[i]<<" "; } return 0; } |