#include<cstdio> #include<vector> #include<algorithm> using namespace std; vector<int> polaczenia[200001]; int poprzednicy[200001]; vector<int> stos, wynik; int n, d, wielk, maks, num; bool odw[200001]; void top_sort() { while(!stos.empty()) { //printf("%d ", stos.back()); int a=stos.back(); odw[a]=true; stos.pop_back(); for(int i=0; i<polaczenia[a].size(); i++) { poprzednicy[polaczenia[a][i]]--; if(!odw[polaczenia[a][i]] && poprzednicy[polaczenia[a][i]]<d) stos.push_back(polaczenia[a][i]); } } } void dfs(int u) { //printf("a"); wielk++; odw[u]=true; for(int i=0; i<polaczenia[u].size(); i++) { int v=polaczenia[u][i]; if(!odw[v] && poprzednicy[v]>=d) dfs(v); } } void dfs2(int u) { wynik.push_back(u); odw[u]=true; for(int i=0; i<polaczenia[u].size(); i++) { int v=polaczenia[u][i]; if(!odw[v] && poprzednicy[v]>=d) dfs2(v); } } int main() { int m, a, b; scanf("%d%d%d", &n, &m, &d); for(int i=0; i<m; i++) { scanf("%d%d", &a, &b); polaczenia[a].push_back(b); polaczenia[b].push_back(a); poprzednicy[a]++; poprzednicy[b]++; } for(int i=1; i<=n; i++) if(poprzednicy[i]<d) stos.push_back(i); top_sort(); for(int i=0; i<=n; i++) odw[i]=false; for(int i=1; i<=n; i++) { if(poprzednicy[i]>=d) dfs(i); if(wielk>maks) { maks=wielk; num=i; wielk=0; } } if(num==0) { printf("NIE"); return 0; } for(int i=0; i<=n; i++) odw[i]=false; dfs2(num); sort(wynik.begin(), wynik.end()); printf("%d\n", maks); for(int i=0; i<maks; i++) printf("%d ", wynik[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 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 | #include<cstdio> #include<vector> #include<algorithm> using namespace std; vector<int> polaczenia[200001]; int poprzednicy[200001]; vector<int> stos, wynik; int n, d, wielk, maks, num; bool odw[200001]; void top_sort() { while(!stos.empty()) { //printf("%d ", stos.back()); int a=stos.back(); odw[a]=true; stos.pop_back(); for(int i=0; i<polaczenia[a].size(); i++) { poprzednicy[polaczenia[a][i]]--; if(!odw[polaczenia[a][i]] && poprzednicy[polaczenia[a][i]]<d) stos.push_back(polaczenia[a][i]); } } } void dfs(int u) { //printf("a"); wielk++; odw[u]=true; for(int i=0; i<polaczenia[u].size(); i++) { int v=polaczenia[u][i]; if(!odw[v] && poprzednicy[v]>=d) dfs(v); } } void dfs2(int u) { wynik.push_back(u); odw[u]=true; for(int i=0; i<polaczenia[u].size(); i++) { int v=polaczenia[u][i]; if(!odw[v] && poprzednicy[v]>=d) dfs2(v); } } int main() { int m, a, b; scanf("%d%d%d", &n, &m, &d); for(int i=0; i<m; i++) { scanf("%d%d", &a, &b); polaczenia[a].push_back(b); polaczenia[b].push_back(a); poprzednicy[a]++; poprzednicy[b]++; } for(int i=1; i<=n; i++) if(poprzednicy[i]<d) stos.push_back(i); top_sort(); for(int i=0; i<=n; i++) odw[i]=false; for(int i=1; i<=n; i++) { if(poprzednicy[i]>=d) dfs(i); if(wielk>maks) { maks=wielk; num=i; wielk=0; } } if(num==0) { printf("NIE"); return 0; } for(int i=0; i<=n; i++) odw[i]=false; dfs2(num); sort(wynik.begin(), wynik.end()); printf("%d\n", maks); for(int i=0; i<maks; i++) printf("%d ", wynik[i]); } |