#include <iostream> #include <vector> #include <queue> #include <algorithm> #define REP(i,n) for(int i=1; i<=(n);++i) #define FORE(i,n) for(__typeof((n).begin()) i=(n).begin();i!=(n).end();++i) #define PB push_back using namespace std; const int maxx=200001; vector<int> miasta[maxx]; vector<bool> jest(maxx); vector<bool> visited(maxx); vector<int> odp_main; vector<int> odp_test; vector<bool> vis(maxx); int main() { int n,m,d,tm1,tm2; cin>>n>>m>>d; REP(i,m) { cin>>tm1>>tm2; miasta[tm1].PB(tm2); miasta[tm2].PB(tm1); } // REP(i,n) //{ //cout<<i<<": "; // FORE(j,miasta[i]) // { // cout<<*j<<" "; // } //cout<<endl; //} queue<int> kol; REP(i,n) if(!vis[i]) { kol.push(i); while(!kol.empty()) { int v=kol.front(); //cout<<v<<endl; kol.pop(); vis[v]=true; FORE(j,miasta[v]) { if(miasta[*j].size()<d) { swap(miasta[v][*j],miasta[v].back()); miasta[v].pop_back(); j--; } } if(miasta[v].size()>=d) { jest[v]=true; } else { jest[v]=false; FORE(j,miasta[v]) { if(jest[*j])kol.push(*j); } } } } //cout<<"RRARA"<<endl; queue<int> kolejka; REP(i,n)if(jest[i] && !visited[i]) { kolejka.push(i); visited[i]=true; while(!kolejka.empty()) { int v=kolejka.front(); // cout<<v<<endl; kolejka.pop(); odp_test.push_back(v); FORE(j,miasta[v]) if(jest[*j] && !visited[*j]) { kolejka.push(*j); visited[*j]=true; } } odp_main=(odp_main.size()>=odp_test.size())?odp_main:odp_test; odp_test.clear(); } //REP(i,n) //{ //cout<<i<<" "<<jest[i]<<": "; //FORE(j,miasta[i]) //{ // cout<<*j<<" "; //} //cout<<endl; //} // cout<<endl; if(odp_main.size()) { sort(odp_main.begin(), odp_main.end()); cout<<odp_main.size()<<endl; REP(i,odp_main.size()) cout<<odp_main[i-1]<<" "; } else cout<<"NIE"; 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 131 132 133 134 135 136 | #include <iostream> #include <vector> #include <queue> #include <algorithm> #define REP(i,n) for(int i=1; i<=(n);++i) #define FORE(i,n) for(__typeof((n).begin()) i=(n).begin();i!=(n).end();++i) #define PB push_back using namespace std; const int maxx=200001; vector<int> miasta[maxx]; vector<bool> jest(maxx); vector<bool> visited(maxx); vector<int> odp_main; vector<int> odp_test; vector<bool> vis(maxx); int main() { int n,m,d,tm1,tm2; cin>>n>>m>>d; REP(i,m) { cin>>tm1>>tm2; miasta[tm1].PB(tm2); miasta[tm2].PB(tm1); } // REP(i,n) //{ //cout<<i<<": "; // FORE(j,miasta[i]) // { // cout<<*j<<" "; // } //cout<<endl; //} queue<int> kol; REP(i,n) if(!vis[i]) { kol.push(i); while(!kol.empty()) { int v=kol.front(); //cout<<v<<endl; kol.pop(); vis[v]=true; FORE(j,miasta[v]) { if(miasta[*j].size()<d) { swap(miasta[v][*j],miasta[v].back()); miasta[v].pop_back(); j--; } } if(miasta[v].size()>=d) { jest[v]=true; } else { jest[v]=false; FORE(j,miasta[v]) { if(jest[*j])kol.push(*j); } } } } //cout<<"RRARA"<<endl; queue<int> kolejka; REP(i,n)if(jest[i] && !visited[i]) { kolejka.push(i); visited[i]=true; while(!kolejka.empty()) { int v=kolejka.front(); // cout<<v<<endl; kolejka.pop(); odp_test.push_back(v); FORE(j,miasta[v]) if(jest[*j] && !visited[*j]) { kolejka.push(*j); visited[*j]=true; } } odp_main=(odp_main.size()>=odp_test.size())?odp_main:odp_test; odp_test.clear(); } //REP(i,n) //{ //cout<<i<<" "<<jest[i]<<": "; //FORE(j,miasta[i]) //{ // cout<<*j<<" "; //} //cout<<endl; //} // cout<<endl; if(odp_main.size()) { sort(odp_main.begin(), odp_main.end()); cout<<odp_main.size()<<endl; REP(i,odp_main.size()) cout<<odp_main[i-1]<<" "; } else cout<<"NIE"; return 0; } |