//Jan Omeljaniuk // #include <list> #include <stack> #include <queue> #include <vector> #include <string> #include <bitset> #include <cassert> #include <iostream> #include <algorithm> #define unm unsigned long long int #define nm long long int #define uint unsigned int //#define debug using namespace std; struct wierzch { uint deg = 0; bool deleted = false; bool odw = false; vector<pair<uint, uint>> d; }; uint n,m,d,a,b; uint maxs=0, maxid; vector<uint> znalezione; vector<wierzch> graf; uint get_size(uint x) { if(graf[x].odw||graf[x].deleted) return 0; graf[x].odw=true; uint sm = 1; for(uint i=0;i<graf[x].d.size();++i) sm += get_size(graf[x].d[i].first); return sm; } void findem(uint x) { if(!graf[x].odw||graf[x].deleted) return; graf[x].odw=false; znalezione.push_back(x); for(uint i=0;i<graf[x].d.size();++i) findem(graf[x].d[i].first); } void fix(uint x){ if(graf[x].deg>=d||graf[x].deleted) return; graf[x].deleted = true; for(uint i=0;i<graf[x].d.size();++i){ const uint celid = graf[x].d[i].first; const uint pathid = graf[x].d[i].second; graf[celid].deg--; //graf[x].deg--; //swap(graf[celid].d[pathid], graf[celid].d[graf[celid].d.size()-1]); //graf[celid].d.pop_back(); fix(celid); } } int main(){ ios_base::sync_with_stdio(false); cin >> n >> m >> d; graf.resize(n+1); for(uint i=0;i<m;++i){ cin >> a >> b; graf[a].d.push_back(make_pair(b, graf[b].d.size())); graf[b].d.push_back(make_pair(a, graf[a].d.size()-1)); graf[a].deg++; graf[b].deg++; } for(uint i=1;i<=n;++i) fix(i); #ifdef debug cerr << "Graf:\n"; for(uint i=1;i<=n;++i){ cerr << i << ".\n"; cerr << "Del: " << ( graf[i].deleted ? "Yup" : "Nope")<<"\n"; cerr << "Deg: " << graf[i].deg << "\n"; cerr << "Sasiedzi:\n"; for(uint j=0;j<graf[i].d.size();++j) cerr << graf[i].d[j].first << " "; cerr << "\n"; } #endif for(uint i=1;i<=n;++i){ const uint temp = get_size(i); if(temp>maxs){ maxs=temp; maxid=i; } } if(maxs==0){ cout << "NIE\n"; return 0; } findem(maxid); sort(znalezione.begin(), znalezione.end()); cout << maxs << "\n"; //#ifdef debug //assert(maxs==znalezione.size()); //#endif for(uint i=0;i<znalezione.size();++i) cout << znalezione[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 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 | //Jan Omeljaniuk // #include <list> #include <stack> #include <queue> #include <vector> #include <string> #include <bitset> #include <cassert> #include <iostream> #include <algorithm> #define unm unsigned long long int #define nm long long int #define uint unsigned int //#define debug using namespace std; struct wierzch { uint deg = 0; bool deleted = false; bool odw = false; vector<pair<uint, uint>> d; }; uint n,m,d,a,b; uint maxs=0, maxid; vector<uint> znalezione; vector<wierzch> graf; uint get_size(uint x) { if(graf[x].odw||graf[x].deleted) return 0; graf[x].odw=true; uint sm = 1; for(uint i=0;i<graf[x].d.size();++i) sm += get_size(graf[x].d[i].first); return sm; } void findem(uint x) { if(!graf[x].odw||graf[x].deleted) return; graf[x].odw=false; znalezione.push_back(x); for(uint i=0;i<graf[x].d.size();++i) findem(graf[x].d[i].first); } void fix(uint x){ if(graf[x].deg>=d||graf[x].deleted) return; graf[x].deleted = true; for(uint i=0;i<graf[x].d.size();++i){ const uint celid = graf[x].d[i].first; const uint pathid = graf[x].d[i].second; graf[celid].deg--; //graf[x].deg--; //swap(graf[celid].d[pathid], graf[celid].d[graf[celid].d.size()-1]); //graf[celid].d.pop_back(); fix(celid); } } int main(){ ios_base::sync_with_stdio(false); cin >> n >> m >> d; graf.resize(n+1); for(uint i=0;i<m;++i){ cin >> a >> b; graf[a].d.push_back(make_pair(b, graf[b].d.size())); graf[b].d.push_back(make_pair(a, graf[a].d.size()-1)); graf[a].deg++; graf[b].deg++; } for(uint i=1;i<=n;++i) fix(i); #ifdef debug cerr << "Graf:\n"; for(uint i=1;i<=n;++i){ cerr << i << ".\n"; cerr << "Del: " << ( graf[i].deleted ? "Yup" : "Nope")<<"\n"; cerr << "Deg: " << graf[i].deg << "\n"; cerr << "Sasiedzi:\n"; for(uint j=0;j<graf[i].d.size();++j) cerr << graf[i].d[j].first << " "; cerr << "\n"; } #endif for(uint i=1;i<=n;++i){ const uint temp = get_size(i); if(temp>maxs){ maxs=temp; maxid=i; } } if(maxs==0){ cout << "NIE\n"; return 0; } findem(maxid); sort(znalezione.begin(), znalezione.end()); cout << maxs << "\n"; //#ifdef debug //assert(maxs==znalezione.size()); //#endif for(uint i=0;i<znalezione.size();++i) cout << znalezione[i] << " "; return 0; } |