#include<cstdio> #include<vector> #include<queue> using namespace std; vector<int> kraw[200010]; queue<int> q; int stop[200010], visited[200010], N1, N, D; void BFS(int u){ q.push(u); int v; while(!q.empty()){ v=q.front(); visited[v]=1; q.pop(); N1--; for(int i=0; i<kraw[v].size(); i++){ stop[kraw[v][i]]--; if(!visited[kraw[v][i]] && stop[kraw[v][i]]<D) q.push(kraw[v][i]); } } return; } int main(){ int M, a, b; scanf("%d%d%d", &N, &M, &D); N1=N; for(int i=0; i<M; i++){ scanf("%d%d", &a, &b); kraw[a].push_back(b); kraw[b].push_back(a); stop[a]++; stop[b]++; } a=0; for(int i=1; i<=N; i++){ if(stop[i]<D && !visited[i]){ BFS(i); } } if(N1<D+1) printf("NIE"); else{ printf("%d\n", N1); for(int i=1; i<=N; i++){ if(visited[i]==0) printf("%d ", i); } } getchar(); getchar(); 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 | #include<cstdio> #include<vector> #include<queue> using namespace std; vector<int> kraw[200010]; queue<int> q; int stop[200010], visited[200010], N1, N, D; void BFS(int u){ q.push(u); int v; while(!q.empty()){ v=q.front(); visited[v]=1; q.pop(); N1--; for(int i=0; i<kraw[v].size(); i++){ stop[kraw[v][i]]--; if(!visited[kraw[v][i]] && stop[kraw[v][i]]<D) q.push(kraw[v][i]); } } return; } int main(){ int M, a, b; scanf("%d%d%d", &N, &M, &D); N1=N; for(int i=0; i<M; i++){ scanf("%d%d", &a, &b); kraw[a].push_back(b); kraw[b].push_back(a); stop[a]++; stop[b]++; } a=0; for(int i=1; i<=N; i++){ if(stop[i]<D && !visited[i]){ BFS(i); } } if(N1<D+1) printf("NIE"); else{ printf("%d\n", N1); for(int i=1; i<=N; i++){ if(visited[i]==0) printf("%d ", i); } } getchar(); getchar(); return 0; } |