//Przemysław Jakub Kozłowski #include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; const int N = 200005; int n,m,d; vector<int> V[N]; int sto[N]; char usu[N]; int czas=1; int mcount; int odw[N]; void DFS(int x) { odw[x] = czas; mcount++; for(int i = 0;i < V[x].size();i++) if(!usu[V[x][i]] && !odw[V[x][i]]) DFS(V[x][i]); } int main() { scanf("%d%d%d", &n, &m, &d); for(int i = 1;i <= m;i++) { int a,b; scanf("%d%d", &a, &b); V[a].push_back(b); V[b].push_back(a); } for(int i = 1;i <= n;i++) sto[i] = V[i].size(); queue<int> Q; for(int i = 1;i <= n;i++) if(sto[i] < d) Q.push(i); while(!Q.empty()) { int q = Q.front(); Q.pop(); usu[q] = 1; for(int i = 0;i < V[q].size();i++) { sto[V[q][i]]--; if(sto[V[q][i]] == d-1) Q.push(V[q][i]); } } int wyncza = 0, wyncnt = 0; for(int i = 1;i <= n;i++) if(!usu[i] && !odw[i]) { ++czas; mcount = 0; DFS(i); if(mcount > wyncnt) { wyncnt = mcount; wyncza = czas; } } if(wyncnt) { printf("%d\n", wyncnt); for(int i = 1;i <= n;i++) if(odw[i] == wyncza) printf("%d ", i); printf("\n"); } else printf("NIE\n"); 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 | //Przemysław Jakub Kozłowski #include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; const int N = 200005; int n,m,d; vector<int> V[N]; int sto[N]; char usu[N]; int czas=1; int mcount; int odw[N]; void DFS(int x) { odw[x] = czas; mcount++; for(int i = 0;i < V[x].size();i++) if(!usu[V[x][i]] && !odw[V[x][i]]) DFS(V[x][i]); } int main() { scanf("%d%d%d", &n, &m, &d); for(int i = 1;i <= m;i++) { int a,b; scanf("%d%d", &a, &b); V[a].push_back(b); V[b].push_back(a); } for(int i = 1;i <= n;i++) sto[i] = V[i].size(); queue<int> Q; for(int i = 1;i <= n;i++) if(sto[i] < d) Q.push(i); while(!Q.empty()) { int q = Q.front(); Q.pop(); usu[q] = 1; for(int i = 0;i < V[q].size();i++) { sto[V[q][i]]--; if(sto[V[q][i]] == d-1) Q.push(V[q][i]); } } int wyncza = 0, wyncnt = 0; for(int i = 1;i <= n;i++) if(!usu[i] && !odw[i]) { ++czas; mcount = 0; DFS(i); if(mcount > wyncnt) { wyncnt = mcount; wyncza = czas; } } if(wyncnt) { printf("%d\n", wyncnt); for(int i = 1;i <= n;i++) if(odw[i] == wyncza) printf("%d ", i); printf("\n"); } else printf("NIE\n"); return 0; } |