#include <iostream> #include <set> #include <map> #include <list> #include <vector> using namespace std; int main(){ int n,m,d,t1,t2; map< int,set<int> > roads; cin >> n >> m >>d; for( int i=0; i<m ; i++){ cin >> t1 >> t2; roads[t1].insert(t2); roads[t2].insert(t1); } map< int, set<int> >:: iterator it; set<int>::iterator it2; //find nodes with roads < d, removing for( it=roads.begin(); it != roads.end(); ++it){ if (it->second.size() < d){ set<int>::iterator it3; for(it3 = it->second.begin(); it3 != it->second.end(); ++it3){ roads[*it3].erase(it->first); } roads.erase(it->first); it=roads.begin(); } } //merging for( it=roads.begin(); it != roads.end(); ++it){ for ( it2=it->second.begin(); it2 != it->second.end(); ++it2){ it->second.insert(roads[*it2].begin(), roads[*it2].end()); roads[*it2].clear(); } } map< int, set<int> >::iterator maxit=roads.begin(); for( it=roads.begin(); it != roads.end(); ++it){ if (it->second.size() > maxit->second.size()){ maxit=it; } } if ( maxit->second.size() > 0 ) { cout<<maxit->second.size()<<endl; for(set<int>::iterator i = maxit->second.begin(); i != maxit->second.end(); ++i){ if ( i != maxit->second.begin() ) cout<<" "; cout<< *i; } cout << endl; } else cout<<"NIE"<<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 | #include <iostream> #include <set> #include <map> #include <list> #include <vector> using namespace std; int main(){ int n,m,d,t1,t2; map< int,set<int> > roads; cin >> n >> m >>d; for( int i=0; i<m ; i++){ cin >> t1 >> t2; roads[t1].insert(t2); roads[t2].insert(t1); } map< int, set<int> >:: iterator it; set<int>::iterator it2; //find nodes with roads < d, removing for( it=roads.begin(); it != roads.end(); ++it){ if (it->second.size() < d){ set<int>::iterator it3; for(it3 = it->second.begin(); it3 != it->second.end(); ++it3){ roads[*it3].erase(it->first); } roads.erase(it->first); it=roads.begin(); } } //merging for( it=roads.begin(); it != roads.end(); ++it){ for ( it2=it->second.begin(); it2 != it->second.end(); ++it2){ it->second.insert(roads[*it2].begin(), roads[*it2].end()); roads[*it2].clear(); } } map< int, set<int> >::iterator maxit=roads.begin(); for( it=roads.begin(); it != roads.end(); ++it){ if (it->second.size() > maxit->second.size()){ maxit=it; } } if ( maxit->second.size() > 0 ) { cout<<maxit->second.size()<<endl; for(set<int>::iterator i = maxit->second.begin(); i != maxit->second.end(); ++i){ if ( i != maxit->second.begin() ) cout<<" "; cout<< *i; } cout << endl; } else cout<<"NIE"<<endl; return 0; } |