#include <iostream> #include <stdlib.h> #include <algorithm> #include <vector> #include <set> using namespace std; struct vertex { vertex() : visited( false ) {} bool visited; set< int > links; }; vector< vertex > verts; int visit( int index ) { int count = 1; vertex& v = verts[ index ]; v.visited = true; for ( set< int >::const_iterator it = v.links.begin(); it != v.links.end(); ++it ) { if ( !verts[ *it ].visited ) { count += visit( *it ); } } return count; } vector< int > result; void visitAndCollect( int index ) { vertex& v = verts[ index ]; result.push_back( index ); v.visited = false; for ( set< int >::const_iterator it = v.links.begin(); it != v.links.end(); ++it ) { if ( verts[ *it ].visited ) { visitAndCollect( *it ); } } } int main() { int n, m, d; cin >> n >> m >> d; verts.resize( n ); for ( int i = 0; i < m; ++i ) { int a, b; cin >> a >> b; --a; --b; verts[ a ].links.insert( b ); verts[ b ].links.insert( a ); } struct pred { bool operator () ( const int a, const int b ) const { const int aLinksSize = verts[ a ].links.size(); const int bLinksSize = verts[ b ].links.size(); return aLinksSize == bLinksSize ? ( a < b ) : ( aLinksSize < bLinksSize ); } }; set< int, pred > vertexIndices; for ( int i = 0; i < n; ++i ) { vertexIndices.insert( i ); } const int s = vertexIndices.size(); while ( !vertexIndices.empty() ) { const set< int, pred >::iterator firstIt = vertexIndices.begin(); const int firstIndex = *firstIt; const vertex& v = verts[ firstIndex ]; if ( ( int ) v.links.size() >= d ) { break; } vertexIndices.erase( firstIt ); for ( set< int >::const_iterator it = v.links.begin(); it != v.links.end(); ++it ) { vertexIndices.erase( *it ); verts[ *it ].links.erase( firstIndex ); vertexIndices.insert( *it ); } } if ( vertexIndices.empty() ) { cout << "NIE"; } else { int bestSetSize = 0; int bestSetStart = -1; for ( set< int, pred >::const_iterator it = vertexIndices.begin(); it != vertexIndices.end(); ++it ) { if ( !verts[ *it ].visited ) { const int setSize = visit( *it ); if ( setSize > bestSetSize ) { bestSetSize = setSize; bestSetStart = *it; } } } visitAndCollect( bestSetStart ); sort( result.begin(), result.end() ); cout << result.size() << endl; for ( unsigned int i = 0; i < result.size(); ++i ) { cout << ( result[ i ] + 1 ) << " "; } } }
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 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 | #include <iostream> #include <stdlib.h> #include <algorithm> #include <vector> #include <set> using namespace std; struct vertex { vertex() : visited( false ) {} bool visited; set< int > links; }; vector< vertex > verts; int visit( int index ) { int count = 1; vertex& v = verts[ index ]; v.visited = true; for ( set< int >::const_iterator it = v.links.begin(); it != v.links.end(); ++it ) { if ( !verts[ *it ].visited ) { count += visit( *it ); } } return count; } vector< int > result; void visitAndCollect( int index ) { vertex& v = verts[ index ]; result.push_back( index ); v.visited = false; for ( set< int >::const_iterator it = v.links.begin(); it != v.links.end(); ++it ) { if ( verts[ *it ].visited ) { visitAndCollect( *it ); } } } int main() { int n, m, d; cin >> n >> m >> d; verts.resize( n ); for ( int i = 0; i < m; ++i ) { int a, b; cin >> a >> b; --a; --b; verts[ a ].links.insert( b ); verts[ b ].links.insert( a ); } struct pred { bool operator () ( const int a, const int b ) const { const int aLinksSize = verts[ a ].links.size(); const int bLinksSize = verts[ b ].links.size(); return aLinksSize == bLinksSize ? ( a < b ) : ( aLinksSize < bLinksSize ); } }; set< int, pred > vertexIndices; for ( int i = 0; i < n; ++i ) { vertexIndices.insert( i ); } const int s = vertexIndices.size(); while ( !vertexIndices.empty() ) { const set< int, pred >::iterator firstIt = vertexIndices.begin(); const int firstIndex = *firstIt; const vertex& v = verts[ firstIndex ]; if ( ( int ) v.links.size() >= d ) { break; } vertexIndices.erase( firstIt ); for ( set< int >::const_iterator it = v.links.begin(); it != v.links.end(); ++it ) { vertexIndices.erase( *it ); verts[ *it ].links.erase( firstIndex ); vertexIndices.insert( *it ); } } if ( vertexIndices.empty() ) { cout << "NIE"; } else { int bestSetSize = 0; int bestSetStart = -1; for ( set< int, pred >::const_iterator it = vertexIndices.begin(); it != vertexIndices.end(); ++it ) { if ( !verts[ *it ].visited ) { const int setSize = visit( *it ); if ( setSize > bestSetSize ) { bestSetSize = setSize; bestSetStart = *it; } } } visitAndCollect( bestSetStart ); sort( result.begin(), result.end() ); cout << result.size() << endl; for ( unsigned int i = 0; i < result.size(); ++i ) { cout << ( result[ i ] + 1 ) << " "; } } } |