#include<iostream> #include<vector> #include<queue> using namespace std; const int N = 300000; int n, m, d, st[N], a, b, maxind, tmp; queue<int> q; vector<int> v[N]; int rem[N], odw[N]; void dfs(int x, int y){ odw[x]=y; tmp++; for(int i=0;i<v[x].size();i++) if(!odw[v[x][i]] && !rem[v[x][i]]) dfs(v[x][i],y); } int main(){ cin>>n>>m>>d; for(int i=0;i<m;i++){ cin>>a>>b; v[a].push_back(b); v[b].push_back(a); st[a]++; st[b]++; } for(int i=1;i<=n;i++) if(st[i]<d) q.push(i); while(!q.empty()){ int x = q.front(); q.pop(); rem[x] = 1; for(int i = 0; i < v[x].size(); i++){ if(st[v[x][i]] == d) q.push(v[x][i]); st[v[x][i]]--; } } int wyn = 0; for(int i=1;i<=n;i++){ tmp = 0; if(!odw[i] && !rem[i]){ dfs(i,i); if(tmp > wyn){ wyn = tmp; maxind = i; } } } if(wyn == 0) cout<<"NIE"; else{ cout<<wyn<<"\n"; for(int i=1;i<=n;i++) if( odw[i]==maxind) cout<<i<<" "; } }
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 | #include<iostream> #include<vector> #include<queue> using namespace std; const int N = 300000; int n, m, d, st[N], a, b, maxind, tmp; queue<int> q; vector<int> v[N]; int rem[N], odw[N]; void dfs(int x, int y){ odw[x]=y; tmp++; for(int i=0;i<v[x].size();i++) if(!odw[v[x][i]] && !rem[v[x][i]]) dfs(v[x][i],y); } int main(){ cin>>n>>m>>d; for(int i=0;i<m;i++){ cin>>a>>b; v[a].push_back(b); v[b].push_back(a); st[a]++; st[b]++; } for(int i=1;i<=n;i++) if(st[i]<d) q.push(i); while(!q.empty()){ int x = q.front(); q.pop(); rem[x] = 1; for(int i = 0; i < v[x].size(); i++){ if(st[v[x][i]] == d) q.push(v[x][i]); st[v[x][i]]--; } } int wyn = 0; for(int i=1;i<=n;i++){ tmp = 0; if(!odw[i] && !rem[i]){ dfs(i,i); if(tmp > wyn){ wyn = tmp; maxind = i; } } } if(wyn == 0) cout<<"NIE"; else{ cout<<wyn<<"\n"; for(int i=1;i<=n;i++) if( odw[i]==maxind) cout<<i<<" "; } } |