#include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; #define MAX 200009 vector <int> v[MAX], result; queue <int> q; bool disabled[MAX]; int tab[MAX], vis[MAX]; int dfs(int w, int par, bool addToResult); int main(){ int n, m, d, a, b; scanf("%d%d%d", &n, &m, &d); for(int i=1; i<=m; i++){ scanf("%d%d", &a, &b); v[a].push_back(b); v[b].push_back(a); tab[a]++; tab[b]++; } for(int i=1; i<=n; i++){ if(tab[i] < d){ q.push(i); disabled[i] = true; } } while(!q.empty()){ int p = q.front(); q.pop(); disabled[p] = true; int tmp; for(int i=0; i<v[p].size(); i++){ tmp = v[p][i]; if(disabled[tmp]) continue; tab[tmp]--; if(tab[tmp] < d){ q.push(tmp); disabled[tmp] = true; } } } int maxiN = 0, maxiW = 0, tmp; for(int i=1; i<=n; i++){ if(!disabled[i] && !vis[i] && (tmp = dfs(i, i, false)) > maxiW){ maxiW = tmp; maxiN = i; } } if(maxiN == 0){ printf("NIE\n"); return 0; } for(int i=0; i<=n; i++) vis[i] = 0; dfs(maxiN, maxiN, true); sort(result.begin(), result.end()); printf("%d\n", result.size()); for(int p : result){ printf("%d ", p); } } int dfs(int w, int par, bool addToResult){ //printf("jestem w %d\n", w); if(addToResult) result.push_back(w); vis[w] = 1; int res = 1, p; for(int i=0; i<v[w].size(); i++){ p = v[w][i]; if(vis[p] || disabled[p])continue; res += dfs(p, w, addToResult); } return res; }
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 <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; #define MAX 200009 vector <int> v[MAX], result; queue <int> q; bool disabled[MAX]; int tab[MAX], vis[MAX]; int dfs(int w, int par, bool addToResult); int main(){ int n, m, d, a, b; scanf("%d%d%d", &n, &m, &d); for(int i=1; i<=m; i++){ scanf("%d%d", &a, &b); v[a].push_back(b); v[b].push_back(a); tab[a]++; tab[b]++; } for(int i=1; i<=n; i++){ if(tab[i] < d){ q.push(i); disabled[i] = true; } } while(!q.empty()){ int p = q.front(); q.pop(); disabled[p] = true; int tmp; for(int i=0; i<v[p].size(); i++){ tmp = v[p][i]; if(disabled[tmp]) continue; tab[tmp]--; if(tab[tmp] < d){ q.push(tmp); disabled[tmp] = true; } } } int maxiN = 0, maxiW = 0, tmp; for(int i=1; i<=n; i++){ if(!disabled[i] && !vis[i] && (tmp = dfs(i, i, false)) > maxiW){ maxiW = tmp; maxiN = i; } } if(maxiN == 0){ printf("NIE\n"); return 0; } for(int i=0; i<=n; i++) vis[i] = 0; dfs(maxiN, maxiN, true); sort(result.begin(), result.end()); printf("%d\n", result.size()); for(int p : result){ printf("%d ", p); } } int dfs(int w, int par, bool addToResult){ //printf("jestem w %d\n", w); if(addToResult) result.push_back(w); vis[w] = 1; int res = 1, p; for(int i=0; i<v[w].size(); i++){ p = v[w][i]; if(vis[p] || disabled[p])continue; res += dfs(p, w, addToResult); } return res; } |