#include <bits/stdc++.h> using namespace std; typedef long long LL; template<typename TH> void debug_vars(const char* data, TH head){ cerr << data << "=" << head << "\n"; } template<typename TH, typename... TA> void debug_vars(const char* data, TH head, TA... tail){ while(*data != ',') cerr << *data++; cerr << "=" << head << ","; debug_vars(data+1, tail...); } #ifdef LOCAL #define debug(...) debug_vars(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (__VA_ARGS__) #endif ///////////////////////////////////////////////////////// const int MaxN = 200005; int N, M, D; vector<int> adj[MaxN]; bool available[MaxN]; bool visited[MaxN]; int curDeg[MaxN]; void input(){ scanf("%d%d%d", &N, &M, &D); for(int i = 0; i < M; i++){ int u, v; scanf("%d%d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); curDeg[u]++; curDeg[v]++; } fill(available+1, available+N+1, true); } void remove_bad_verts(){ queue<int> Q; for(int i = 1; i <= N; i++){ if(curDeg[i] < D) Q.push(i); } while(!Q.empty()){ int v = Q.front(); Q.pop(); available[v] = false; for(int s : adj[v]){ if(!available[s]) continue; if(curDeg[s] == D) Q.push(s); curDeg[s]--; } } } vector<int> largestComp; vector<int> curComp; void dfs(int v){ visited[v] = true; curComp.push_back(v); for(int s : adj[v]){ if(available[s] && !visited[s]) dfs(s); } } void find_largest_component(){ for(int v = 1; v <= N; v++){ if(available[v] && !visited[v]){ curComp.clear(); dfs(v); if(curComp.size() > largestComp.size()){ largestComp = curComp; } } } } void output(){ if(largestComp.size() == 0){ printf("NIE\n"); return; } printf("%zu\n", largestComp.size()); sort(largestComp.begin(), largestComp.end()); for(int v : largestComp) printf("%d ", v); printf("\n"); } int main(){ input(); remove_bad_verts(); find_largest_component(); output(); }
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; typedef long long LL; template<typename TH> void debug_vars(const char* data, TH head){ cerr << data << "=" << head << "\n"; } template<typename TH, typename... TA> void debug_vars(const char* data, TH head, TA... tail){ while(*data != ',') cerr << *data++; cerr << "=" << head << ","; debug_vars(data+1, tail...); } #ifdef LOCAL #define debug(...) debug_vars(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (__VA_ARGS__) #endif ///////////////////////////////////////////////////////// const int MaxN = 200005; int N, M, D; vector<int> adj[MaxN]; bool available[MaxN]; bool visited[MaxN]; int curDeg[MaxN]; void input(){ scanf("%d%d%d", &N, &M, &D); for(int i = 0; i < M; i++){ int u, v; scanf("%d%d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); curDeg[u]++; curDeg[v]++; } fill(available+1, available+N+1, true); } void remove_bad_verts(){ queue<int> Q; for(int i = 1; i <= N; i++){ if(curDeg[i] < D) Q.push(i); } while(!Q.empty()){ int v = Q.front(); Q.pop(); available[v] = false; for(int s : adj[v]){ if(!available[s]) continue; if(curDeg[s] == D) Q.push(s); curDeg[s]--; } } } vector<int> largestComp; vector<int> curComp; void dfs(int v){ visited[v] = true; curComp.push_back(v); for(int s : adj[v]){ if(available[s] && !visited[s]) dfs(s); } } void find_largest_component(){ for(int v = 1; v <= N; v++){ if(available[v] && !visited[v]){ curComp.clear(); dfs(v); if(curComp.size() > largestComp.size()){ largestComp = curComp; } } } } void output(){ if(largestComp.size() == 0){ printf("NIE\n"); return; } printf("%zu\n", largestComp.size()); sort(largestComp.begin(), largestComp.end()); for(int v : largestComp) printf("%d ", v); printf("\n"); } int main(){ input(); remove_bad_verts(); find_largest_component(); output(); } |