#include<bits/stdc++.h> using namespace std; #define REP(i, n) for(int i = 0; i < (n); i++) #define SIZE(s) ((int) (s).size()) #define ALL(s) s.begin(), s.end() #define MP make_pair #define ST first #define ND second using PII = pair<int, int>; const int N = 2e5; int n, m, d; vector<int> g[N]; int deg[N]; bool visited[N]; vector<int> toremove; vector<int> cc; void dfs(int u){ cc.push_back(u); visited[u] = true; for(int v : g[u]) if(!visited[v]) dfs(v); } int main(){ assert(scanf("%d%d%d", &n, &m, &d) == 3); REP(i, m){ int ai, bi; assert(scanf("%d%d", &ai, &bi) == 2); --ai; --bi; g[ai].push_back(bi); g[bi].push_back(ai); } REP(u, n){ deg[u] = g[u].size(); if(deg[u] < d){ toremove.push_back(u); } } REP(i, SIZE(toremove)) { int u = toremove[i]; visited[u] = true; for(int v : g[u]){ if(deg[v]-- == d){ toremove.push_back(v); } } } vector<int> maxcc; REP(u, n) if(!visited[u]){ cc.clear(); dfs(u); if(cc.size() > maxcc.size()) maxcc = cc; } if(maxcc.empty()){ printf("NIE\n"); } else { sort(ALL(maxcc)); printf("%d\n", SIZE(maxcc)); for(auto v : maxcc) printf("%d ", v + 1); 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 | #include<bits/stdc++.h> using namespace std; #define REP(i, n) for(int i = 0; i < (n); i++) #define SIZE(s) ((int) (s).size()) #define ALL(s) s.begin(), s.end() #define MP make_pair #define ST first #define ND second using PII = pair<int, int>; const int N = 2e5; int n, m, d; vector<int> g[N]; int deg[N]; bool visited[N]; vector<int> toremove; vector<int> cc; void dfs(int u){ cc.push_back(u); visited[u] = true; for(int v : g[u]) if(!visited[v]) dfs(v); } int main(){ assert(scanf("%d%d%d", &n, &m, &d) == 3); REP(i, m){ int ai, bi; assert(scanf("%d%d", &ai, &bi) == 2); --ai; --bi; g[ai].push_back(bi); g[bi].push_back(ai); } REP(u, n){ deg[u] = g[u].size(); if(deg[u] < d){ toremove.push_back(u); } } REP(i, SIZE(toremove)) { int u = toremove[i]; visited[u] = true; for(int v : g[u]){ if(deg[v]-- == d){ toremove.push_back(v); } } } vector<int> maxcc; REP(u, n) if(!visited[u]){ cc.clear(); dfs(u); if(cc.size() > maxcc.size()) maxcc = cc; } if(maxcc.empty()){ printf("NIE\n"); } else { sort(ALL(maxcc)); printf("%d\n", SIZE(maxcc)); for(auto v : maxcc) printf("%d ", v + 1); printf("\n"); } return 0; } |