//Piotr Pusz #include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; int miasta, drogi, d,a,b,gora, gdzie, licznik, cowybrac, numer,maks; int wychodzi[300000]; priority_queue < pair <int, int> > kopiec; vector <int> sasiedzi[300000]; bool wywalone[300000]; int skladowa[300000]; vector <int> skladowe[300000]; void dfs (int v) { skladowa[v]=numer; ++licznik; skladowe[numer].push_back(v); for (int i=0; i<sasiedzi[v].size(); ++i) { if (wywalone[sasiedzi[v][i]]==1 || skladowa[sasiedzi[v][i]]!=0) continue; skladowa[sasiedzi[v][i]]=numer; //++licznik; dfs(sasiedzi[v][i]); } } int main() { ios_base::sync_with_stdio(0); cin>>miasta>>drogi>>d; for (int i=0; i<drogi; ++i) { cin>>a>>b; if (a!=b) { ++wychodzi[a]; ++wychodzi[b]; sasiedzi[a].push_back(b); sasiedzi[b].push_back(a); } } for (int i=1; i<=miasta; ++i) { kopiec.push(make_pair(-wychodzi[i], i)); //cout<<":"<<-wychodzi[i]<<' '<<i<<endl; } //cout<<kopiec.top(); gora=-kopiec.top().first; while (!kopiec.empty() && gora<d) { gdzie=kopiec.top().second; kopiec.pop(); //cout<<"{}"<<gdzie<<' '<<gora<<' '<<wychodzi[gdzie]<<endl; if (wywalone[gdzie]==1 || gora!=wychodzi[gdzie]) { if (!kopiec.empty()) gora=-kopiec.top().first; continue; } for (int i=0; i<sasiedzi[gdzie].size(); ++i) { if (wywalone[sasiedzi[gdzie][i]]==0) { --wychodzi[sasiedzi[gdzie][i]]; kopiec.push(make_pair(-wychodzi[sasiedzi[gdzie][i]], sasiedzi[gdzie][i])); } } wychodzi[gdzie]=0; sasiedzi[gdzie].clear(); wywalone[gdzie]=1; //cout<<"!"<<gdzie<<endl; if (!kopiec.empty()) gora=-kopiec.top().first; } //for (int i=1; i<=miasta; ++i) cout<<wywalone[i]<<' '; //cout<<endl; for (int i=1; i<=miasta; ++i) { //cout<<"{}"<<i<<' '<<wywalone[i]<<' '<<skladowa[i]<<endl; if (wywalone[i]==1 || skladowa[i]!=0) continue; //cout<<"A"<<endl; ++numer; licznik=0; //cout<<"!"<<i<<' '<<numer<<endl; dfs(i); if (skladowe[numer].size()>maks) { maks=skladowe[numer].size(); cowybrac=numer; } } if (cowybrac==0) cout<<"NIE"; else { sort(skladowe[cowybrac].begin(), skladowe[cowybrac].end()); cout<<skladowe[cowybrac].size()<<"\n"; for (int i=0; i<skladowe[cowybrac].size(); ++i) { cout<<skladowe[cowybrac][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 | //Piotr Pusz #include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; int miasta, drogi, d,a,b,gora, gdzie, licznik, cowybrac, numer,maks; int wychodzi[300000]; priority_queue < pair <int, int> > kopiec; vector <int> sasiedzi[300000]; bool wywalone[300000]; int skladowa[300000]; vector <int> skladowe[300000]; void dfs (int v) { skladowa[v]=numer; ++licznik; skladowe[numer].push_back(v); for (int i=0; i<sasiedzi[v].size(); ++i) { if (wywalone[sasiedzi[v][i]]==1 || skladowa[sasiedzi[v][i]]!=0) continue; skladowa[sasiedzi[v][i]]=numer; //++licznik; dfs(sasiedzi[v][i]); } } int main() { ios_base::sync_with_stdio(0); cin>>miasta>>drogi>>d; for (int i=0; i<drogi; ++i) { cin>>a>>b; if (a!=b) { ++wychodzi[a]; ++wychodzi[b]; sasiedzi[a].push_back(b); sasiedzi[b].push_back(a); } } for (int i=1; i<=miasta; ++i) { kopiec.push(make_pair(-wychodzi[i], i)); //cout<<":"<<-wychodzi[i]<<' '<<i<<endl; } //cout<<kopiec.top(); gora=-kopiec.top().first; while (!kopiec.empty() && gora<d) { gdzie=kopiec.top().second; kopiec.pop(); //cout<<"{}"<<gdzie<<' '<<gora<<' '<<wychodzi[gdzie]<<endl; if (wywalone[gdzie]==1 || gora!=wychodzi[gdzie]) { if (!kopiec.empty()) gora=-kopiec.top().first; continue; } for (int i=0; i<sasiedzi[gdzie].size(); ++i) { if (wywalone[sasiedzi[gdzie][i]]==0) { --wychodzi[sasiedzi[gdzie][i]]; kopiec.push(make_pair(-wychodzi[sasiedzi[gdzie][i]], sasiedzi[gdzie][i])); } } wychodzi[gdzie]=0; sasiedzi[gdzie].clear(); wywalone[gdzie]=1; //cout<<"!"<<gdzie<<endl; if (!kopiec.empty()) gora=-kopiec.top().first; } //for (int i=1; i<=miasta; ++i) cout<<wywalone[i]<<' '; //cout<<endl; for (int i=1; i<=miasta; ++i) { //cout<<"{}"<<i<<' '<<wywalone[i]<<' '<<skladowa[i]<<endl; if (wywalone[i]==1 || skladowa[i]!=0) continue; //cout<<"A"<<endl; ++numer; licznik=0; //cout<<"!"<<i<<' '<<numer<<endl; dfs(i); if (skladowe[numer].size()>maks) { maks=skladowe[numer].size(); cowybrac=numer; } } if (cowybrac==0) cout<<"NIE"; else { sort(skladowe[cowybrac].begin(), skladowe[cowybrac].end()); cout<<skladowe[cowybrac].size()<<"\n"; for (int i=0; i<skladowe[cowybrac].size(); ++i) { cout<<skladowe[cowybrac][i]<<' '; } } return 0; } |