#include <iostream> #include <cstdio> #include <list> #include <vector> #include <set> using namespace std; list<int> l; vector< set<int> > s(200001, set<int>()); int visited[200001]; int dfs(int i, int group, int d) { int res = 0; //printf("node %d, edges %d\n", i, s[i].size()); if(visited[i] > 0 || s[i].size() < d) return 0; visited[i] = group; res+=1; for (std::set<int>::iterator it=s[i].begin(); it!=s[i].end(); ++it) { res += dfs(*it, group, d); } return res; } int main() { int n, m, d; scanf("%d %d %d", &n, &m, &d); int from, to; for(int i = 0; i < m; i++) { scanf("%d %d", &from, &to); s[from].insert(to); s[to].insert(from); l.push_back(from); l.push_back(to); } while(!l.empty()) { int v = l.front(); l.pop_front(); if (s[v].size() < d) { //printf("rm %d\n", s[v].size()); for (std::set<int>::iterator it=s[v].begin(); it!=s[v].end(); ++it) { int w = *it; s[w].erase(v); l.push_back(w); } s[v].clear(); } } int best = 0; int best_group = -1; int group = 1; for(int i = 1; i <= n; i++) { int count = dfs(i, group, d); if(count > best) { best = count; best_group = group; } group++; } if(best == 0) { printf("NIE\n"); } else { printf("%d\n", best); for(int i = 1; i <= n; i++) { if(visited[i] == best_group) printf("%d ", i); } printf("\n"); } 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 | #include <iostream> #include <cstdio> #include <list> #include <vector> #include <set> using namespace std; list<int> l; vector< set<int> > s(200001, set<int>()); int visited[200001]; int dfs(int i, int group, int d) { int res = 0; //printf("node %d, edges %d\n", i, s[i].size()); if(visited[i] > 0 || s[i].size() < d) return 0; visited[i] = group; res+=1; for (std::set<int>::iterator it=s[i].begin(); it!=s[i].end(); ++it) { res += dfs(*it, group, d); } return res; } int main() { int n, m, d; scanf("%d %d %d", &n, &m, &d); int from, to; for(int i = 0; i < m; i++) { scanf("%d %d", &from, &to); s[from].insert(to); s[to].insert(from); l.push_back(from); l.push_back(to); } while(!l.empty()) { int v = l.front(); l.pop_front(); if (s[v].size() < d) { //printf("rm %d\n", s[v].size()); for (std::set<int>::iterator it=s[v].begin(); it!=s[v].end(); ++it) { int w = *it; s[w].erase(v); l.push_back(w); } s[v].clear(); } } int best = 0; int best_group = -1; int group = 1; for(int i = 1; i <= n; i++) { int count = dfs(i, group, d); if(count > best) { best = count; best_group = group; } group++; } if(best == 0) { printf("NIE\n"); } else { printf("%d\n", best); for(int i = 1; i <= n; i++) { if(visited[i] == best_group) printf("%d ", i); } printf("\n"); } return 0; } |