#include<bits/stdc++.h> using namespace std; struct Para{ int x, y; bool operator<( const Para &o )const{ if( x!=o.x ) return x<o.x; if( y!=o.y ) return y<o.y; return false; } }; int n, m, k, a, b, odw[200111], w[200111], akt = 1; set<int> s[200111]; set<Para> p; queue<int> Q; int main() { scanf("%d%d%d", &n, &m, &k); for( int i = 0; i<m; i++ ){ scanf("%d%d", &a, &b); s[a].insert(b); s[b].insert(a); } for( int i = 1; i<=n; i++ ) p.insert({s[i].size(), i}); set<int>::iterator iTs; while( !p.empty() && p.begin()->x<k){ int X = p.begin()->x; int Y = p.begin()->y; for( iTs = s[Y].begin(); iTs!=s[Y].end(); iTs++ ){ if( s[*iTs].size()-1 > 0 ) p.insert({s[*iTs].size()-1, *iTs}); if( p.find({s[*iTs].size(), *iTs})!=p.end() ) p.erase(p.find({s[*iTs].size(), *iTs})); if( s[*iTs].find(Y)!=s[*iTs].end() ) s[*iTs].erase(s[*iTs].find(Y)); } s[Y].clear(); if( p.find({X, Y})!=p.end() ) p.erase(p.find({X, Y})); } int l = 1; int a = 0; int mx = 0; for( int i = 1; i<=n; i++ ){ if( odw[i]!=0 ) continue; Q.push(i); odw[i] = akt; l = 1; while( !Q.empty() ){ int w = Q.front(); Q.pop(); for( iTs = s[w].begin(); iTs!=s[w].end(); iTs++ ){ if( odw[*iTs]==0 ){ odw[*iTs] = akt; Q.push(*iTs); l++; } } } if( l>mx ){ mx = l; a = akt; } akt++; } if( p.empty() ){ printf("NIE"); return 0; } printf("%d\n", mx); for( int i = 1; i<200111; i++ ) if( odw[i]==a ) printf("%d ", i); 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 | #include<bits/stdc++.h> using namespace std; struct Para{ int x, y; bool operator<( const Para &o )const{ if( x!=o.x ) return x<o.x; if( y!=o.y ) return y<o.y; return false; } }; int n, m, k, a, b, odw[200111], w[200111], akt = 1; set<int> s[200111]; set<Para> p; queue<int> Q; int main() { scanf("%d%d%d", &n, &m, &k); for( int i = 0; i<m; i++ ){ scanf("%d%d", &a, &b); s[a].insert(b); s[b].insert(a); } for( int i = 1; i<=n; i++ ) p.insert({s[i].size(), i}); set<int>::iterator iTs; while( !p.empty() && p.begin()->x<k){ int X = p.begin()->x; int Y = p.begin()->y; for( iTs = s[Y].begin(); iTs!=s[Y].end(); iTs++ ){ if( s[*iTs].size()-1 > 0 ) p.insert({s[*iTs].size()-1, *iTs}); if( p.find({s[*iTs].size(), *iTs})!=p.end() ) p.erase(p.find({s[*iTs].size(), *iTs})); if( s[*iTs].find(Y)!=s[*iTs].end() ) s[*iTs].erase(s[*iTs].find(Y)); } s[Y].clear(); if( p.find({X, Y})!=p.end() ) p.erase(p.find({X, Y})); } int l = 1; int a = 0; int mx = 0; for( int i = 1; i<=n; i++ ){ if( odw[i]!=0 ) continue; Q.push(i); odw[i] = akt; l = 1; while( !Q.empty() ){ int w = Q.front(); Q.pop(); for( iTs = s[w].begin(); iTs!=s[w].end(); iTs++ ){ if( odw[*iTs]==0 ){ odw[*iTs] = akt; Q.push(*iTs); l++; } } } if( l>mx ){ mx = l; a = akt; } akt++; } if( p.empty() ){ printf("NIE"); return 0; } printf("%d\n", mx); for( int i = 1; i<200111; i++ ) if( odw[i]==a ) printf("%d ", i); return 0; } |