#include <iostream> #include <algorithm> #include <list> #include <vector> using namespace std; const int MAX = 200001; struct Algorithm { int n,m,d; vector<list<int> > g; bool active[MAX]; int visited[MAX] = {0,}; int best = 0; int bestCounter = 0; void removeCity(int c) { active[c] = false; for(list<int>::iterator it=g[c].begin(); it != g[c].end(); ++it){ if (active[*it]) { g[*it].remove(c); if (g[*it].size() < d) { removeCity(*it); } } } } int citiesTour(int c, int flag) { int count = 1; visited[c] = flag; for(list<int>::iterator it=g[c].begin(); it != g[c].end(); ++it){ if (active[*it] && visited[*it]==0) { count += citiesTour(*it, flag); } } return count; } void solve() { cin >> n; cin >> m; cin >> d; g.resize(n+1); for (int i = 1; i <= n; ++i) { active[i] = true; } int a,b; for (int i = 0; i < m; ++i) { cin >> a; cin >>b; g[a].push_back(b); g[b].push_back(a); } for (int i = 1; i <= n; ++i) { if (active[i] && g[i].size() < d) { removeCity(i); } } int flag=1; int counter=0; for (int i = 1; i <= n; ++i) { if (active[i] && visited[i]==0) { counter = citiesTour(i, flag); if (counter > bestCounter) { bestCounter = counter; best = flag; } flag++; } } //delete [] g; if (best == 0) { cout << "NIE\n"; return; } cout << bestCounter << "\n"; for (int i = 1; i <= n; ++i) { if (visited[i] == best) { cout << i << " "; } } cout << "\n"; } }; int main() { ios_base::sync_with_stdio(false); Algorithm alg; alg.solve(); 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 | #include <iostream> #include <algorithm> #include <list> #include <vector> using namespace std; const int MAX = 200001; struct Algorithm { int n,m,d; vector<list<int> > g; bool active[MAX]; int visited[MAX] = {0,}; int best = 0; int bestCounter = 0; void removeCity(int c) { active[c] = false; for(list<int>::iterator it=g[c].begin(); it != g[c].end(); ++it){ if (active[*it]) { g[*it].remove(c); if (g[*it].size() < d) { removeCity(*it); } } } } int citiesTour(int c, int flag) { int count = 1; visited[c] = flag; for(list<int>::iterator it=g[c].begin(); it != g[c].end(); ++it){ if (active[*it] && visited[*it]==0) { count += citiesTour(*it, flag); } } return count; } void solve() { cin >> n; cin >> m; cin >> d; g.resize(n+1); for (int i = 1; i <= n; ++i) { active[i] = true; } int a,b; for (int i = 0; i < m; ++i) { cin >> a; cin >>b; g[a].push_back(b); g[b].push_back(a); } for (int i = 1; i <= n; ++i) { if (active[i] && g[i].size() < d) { removeCity(i); } } int flag=1; int counter=0; for (int i = 1; i <= n; ++i) { if (active[i] && visited[i]==0) { counter = citiesTour(i, flag); if (counter > bestCounter) { bestCounter = counter; best = flag; } flag++; } } //delete [] g; if (best == 0) { cout << "NIE\n"; return; } cout << bestCounter << "\n"; for (int i = 1; i <= n; ++i) { if (visited[i] == best) { cout << i << " "; } } cout << "\n"; } }; int main() { ios_base::sync_with_stdio(false); Algorithm alg; alg.solve(); return 0; } |