#include<iostream> #include<vector> using namespace std; const int maxn = 200001; int n, m, d, a, b; vector< int > graph[ maxn ]; int degs[ maxn ], cc[ maxn ]; int best_cc = -1, best_cc_score = -1; void dfs( int start, int id ) { vector< int > q; q.push_back( start ); while( !q.empty() ) { int me = q.back(); q.pop_back(); cc[ me ] = id; for( vector< int >::iterator it = graph[ me ].begin(); it != graph[ me ].end(); it++ ) { if( cc[ (*it) ] == 0 ) q.push_back( (*it) ); } } return; } int main() { cin >> n >> m >> d; for( int i = 0; i < m; i++ ) { cin >> a >> b; a--; b--; graph[ a ].push_back( b ); graph[ b ].push_back( a ); } vector< int > rm; for( int i = 0; i < n; i++ ) { degs[ i ] = graph[ i ].size(); if( degs[ i ] < d ) { rm.push_back( i ); cc[ i ] = -1; } } while( !rm.empty() ) { int t = rm.back(); rm.pop_back(); for( vector< int >::iterator it = graph[ t ].begin(); it != graph[ t ].end(); it++ ) { if( degs[ *it ] == d ) { rm.push_back( *it ); cc[ *it ] = -1; } degs[ *it ]--; } } int num = 0; for( int i = 0; i < n; i++ ) { degs[ i ] = 0; if( cc[ i ] == 0 ) dfs( i, ++num ); } for( int i = 0; i < n; i++ ) { if( cc[ i ] > 0 ) { degs[ cc[ i ] ]++; if( degs[ cc[ i ] ] > best_cc_score ) { best_cc = cc[ i ]; best_cc_score = degs[ cc[ i ] ]; } } } if( best_cc == -1 ) { cout << "NIE" << endl; return 0; } cout << best_cc_score << endl; for( int i = 0; i < n; i++ ) { if( cc[ i ] == best_cc ) cout << i + 1 << " "; } cout << endl; 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 | #include<iostream> #include<vector> using namespace std; const int maxn = 200001; int n, m, d, a, b; vector< int > graph[ maxn ]; int degs[ maxn ], cc[ maxn ]; int best_cc = -1, best_cc_score = -1; void dfs( int start, int id ) { vector< int > q; q.push_back( start ); while( !q.empty() ) { int me = q.back(); q.pop_back(); cc[ me ] = id; for( vector< int >::iterator it = graph[ me ].begin(); it != graph[ me ].end(); it++ ) { if( cc[ (*it) ] == 0 ) q.push_back( (*it) ); } } return; } int main() { cin >> n >> m >> d; for( int i = 0; i < m; i++ ) { cin >> a >> b; a--; b--; graph[ a ].push_back( b ); graph[ b ].push_back( a ); } vector< int > rm; for( int i = 0; i < n; i++ ) { degs[ i ] = graph[ i ].size(); if( degs[ i ] < d ) { rm.push_back( i ); cc[ i ] = -1; } } while( !rm.empty() ) { int t = rm.back(); rm.pop_back(); for( vector< int >::iterator it = graph[ t ].begin(); it != graph[ t ].end(); it++ ) { if( degs[ *it ] == d ) { rm.push_back( *it ); cc[ *it ] = -1; } degs[ *it ]--; } } int num = 0; for( int i = 0; i < n; i++ ) { degs[ i ] = 0; if( cc[ i ] == 0 ) dfs( i, ++num ); } for( int i = 0; i < n; i++ ) { if( cc[ i ] > 0 ) { degs[ cc[ i ] ]++; if( degs[ cc[ i ] ] > best_cc_score ) { best_cc = cc[ i ]; best_cc_score = degs[ cc[ i ] ]; } } } if( best_cc == -1 ) { cout << "NIE" << endl; return 0; } cout << best_cc_score << endl; for( int i = 0; i < n; i++ ) { if( cc[ i ] == best_cc ) cout << i + 1 << " "; } cout << endl; return 0; } |