#include<bits/stdc++.h> using namespace std; const int MAXN = 200010; int n, m, d; vector<int> v[MAXN]; int __count[MAXN], color[MAXN], clrcnt[MAXN]; bool vis[MAXN]; void remove_dfs(int x) { // cout << "WYWALAM " << x << endl; __count[x] = 0; vis[x] = true; for(auto a : v[x]) { if(__count[a]) { __count[a]--; // cout << "-> ZMNIEJSZAM " << a << " ZOSTAŁO " << __count[a] << endl; if(__count[a] < d)remove_dfs(a); } } } //23 //3 4 5 6 7 8 9 10 13 14 15 16 17 18 20 21 22 23 25 27 28 29 30 void dfs(int x) { // cout << "DFS " << x << endl; vis[x] = true; if(__count[x] < d) { remove_dfs(x); return; } else { for(auto a : v[x]) { if(__count[a] && !vis[a]) { dfs(a); } } } } void count_dfs(int x, int clr) { color[x] = clr; clrcnt[clr]++; for(auto a : v[x]) { if(!color[a] && __count[a])count_dfs(a, clr); } } int main() { cin >> n >> m >> d; for(int i = 0; i < m; i++) { int x, y; cin >> x >> y; v[x].push_back(y); v[y].push_back(x); __count[x]++; __count[y]++; } for(int i = 1; i <= n; i++) { if(!vis[i])dfs(i); } for(int i = 1; i <= n; i++) { if(!color[i] && __count[i])count_dfs(i, i); } for(int i = 1; i <= n; i++) { // cout << i << " -> " << __count[i] << ' ' << color[i] << ' ' << clrcnt[i] << endl; } int clrmax = 0, clr = 0; for(int i = 1; i <= n; i++) { if(clrcnt[i] > clrmax) { clrmax = clrcnt[i]; clr = i; } } if(clrmax) { cout << clrmax << '\n'; for(int i = 1; i <= n; i++) { if(color[i] == clr)cout << i << ' '; } // cout << '\n'; } else cout << "NIE\n"; }
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<bits/stdc++.h> using namespace std; const int MAXN = 200010; int n, m, d; vector<int> v[MAXN]; int __count[MAXN], color[MAXN], clrcnt[MAXN]; bool vis[MAXN]; void remove_dfs(int x) { // cout << "WYWALAM " << x << endl; __count[x] = 0; vis[x] = true; for(auto a : v[x]) { if(__count[a]) { __count[a]--; // cout << "-> ZMNIEJSZAM " << a << " ZOSTAŁO " << __count[a] << endl; if(__count[a] < d)remove_dfs(a); } } } //23 //3 4 5 6 7 8 9 10 13 14 15 16 17 18 20 21 22 23 25 27 28 29 30 void dfs(int x) { // cout << "DFS " << x << endl; vis[x] = true; if(__count[x] < d) { remove_dfs(x); return; } else { for(auto a : v[x]) { if(__count[a] && !vis[a]) { dfs(a); } } } } void count_dfs(int x, int clr) { color[x] = clr; clrcnt[clr]++; for(auto a : v[x]) { if(!color[a] && __count[a])count_dfs(a, clr); } } int main() { cin >> n >> m >> d; for(int i = 0; i < m; i++) { int x, y; cin >> x >> y; v[x].push_back(y); v[y].push_back(x); __count[x]++; __count[y]++; } for(int i = 1; i <= n; i++) { if(!vis[i])dfs(i); } for(int i = 1; i <= n; i++) { if(!color[i] && __count[i])count_dfs(i, i); } for(int i = 1; i <= n; i++) { // cout << i << " -> " << __count[i] << ' ' << color[i] << ' ' << clrcnt[i] << endl; } int clrmax = 0, clr = 0; for(int i = 1; i <= n; i++) { if(clrcnt[i] > clrmax) { clrmax = clrcnt[i]; clr = i; } } if(clrmax) { cout << clrmax << '\n'; for(int i = 1; i <= n; i++) { if(color[i] == clr)cout << i << ' '; } // cout << '\n'; } else cout << "NIE\n"; } |