#include <bits/stdc++.h> #define LL long long int #define ULL unsigned long long int #define REP(i, n) for(int i = 0; i < (n); ++i) #define FOR(i, f, n) for(int i = (f); i <= (n); ++i) using namespace std; const int N = 200005; int edgesCount[N]; vector<int> g[N]; bool czyZly[N]; vector<int> maxSkladowa; vector<int> currSkladowa; bool bylem[N]; int bfs(int v) { deque<int> q; currSkladowa.clear(); q.push_back(v); currSkladowa.push_back(v); bylem[v] = true; while(!q.empty()) { int c = q.front(); q.pop_front(); for(int i = 0; i < g[c].size(); ++i) { int u = g[c][i]; if(czyZly[u] || bylem[u]) continue; bylem[u] = true; currSkladowa.push_back(u); q.push_back(u); } } return currSkladowa.size(); } int main() { int n, m, d, a, b; scanf("%d%d%d", &n, &m, &d); REP(i, m) { scanf("%d%d", &a, &b); g[a].push_back(b); g[b].push_back(a); ++edgesCount[a]; ++edgesCount[b]; } vector<int> zle; FOR(i, 1, n) { if(edgesCount[i] < d) { zle.push_back(i); czyZly[i] = true; } } for(int i = 0; i < zle.size(); ++i) { int c = zle[i]; for(int j = 0; j < g[c].size(); ++j) { int u = g[c][j]; --edgesCount[u]; if(!czyZly[u] && edgesCount[u] < d) { czyZly[u] = true; zle.push_back(u); } } } int maxi = 0; FOR(i, 1, n) { if(!czyZly[i] && !bylem[i]) { int b = bfs(i); if(b > maxi) { maxi = b; maxSkladowa.clear(); maxSkladowa.insert(maxSkladowa.begin(), currSkladowa.begin(), currSkladowa.end()); } } } if(maxi == 0) { printf("NIE\n"); return 0; } sort(maxSkladowa.begin(), maxSkladowa.end()); printf("%d\n", maxi); REP(i, maxi) printf("%d ", maxSkladowa[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 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 107 108 109 110 111 112 113 | #include <bits/stdc++.h> #define LL long long int #define ULL unsigned long long int #define REP(i, n) for(int i = 0; i < (n); ++i) #define FOR(i, f, n) for(int i = (f); i <= (n); ++i) using namespace std; const int N = 200005; int edgesCount[N]; vector<int> g[N]; bool czyZly[N]; vector<int> maxSkladowa; vector<int> currSkladowa; bool bylem[N]; int bfs(int v) { deque<int> q; currSkladowa.clear(); q.push_back(v); currSkladowa.push_back(v); bylem[v] = true; while(!q.empty()) { int c = q.front(); q.pop_front(); for(int i = 0; i < g[c].size(); ++i) { int u = g[c][i]; if(czyZly[u] || bylem[u]) continue; bylem[u] = true; currSkladowa.push_back(u); q.push_back(u); } } return currSkladowa.size(); } int main() { int n, m, d, a, b; scanf("%d%d%d", &n, &m, &d); REP(i, m) { scanf("%d%d", &a, &b); g[a].push_back(b); g[b].push_back(a); ++edgesCount[a]; ++edgesCount[b]; } vector<int> zle; FOR(i, 1, n) { if(edgesCount[i] < d) { zle.push_back(i); czyZly[i] = true; } } for(int i = 0; i < zle.size(); ++i) { int c = zle[i]; for(int j = 0; j < g[c].size(); ++j) { int u = g[c][j]; --edgesCount[u]; if(!czyZly[u] && edgesCount[u] < d) { czyZly[u] = true; zle.push_back(u); } } } int maxi = 0; FOR(i, 1, n) { if(!czyZly[i] && !bylem[i]) { int b = bfs(i); if(b > maxi) { maxi = b; maxSkladowa.clear(); maxSkladowa.insert(maxSkladowa.begin(), currSkladowa.begin(), currSkladowa.end()); } } } if(maxi == 0) { printf("NIE\n"); return 0; } sort(maxSkladowa.begin(), maxSkladowa.end()); printf("%d\n", maxi); REP(i, maxi) printf("%d ", maxSkladowa[i]); printf("\n"); return 0; } |