#include <stdio.h> #include <list> #include <iostream> int n,m,d; std::list<int> miasta[200001]; int ile[200001]={0}; int odw[200001]={0}; int s[200001]={0}; int miast_max=-1; int max=0; void scan(int miasto, int ozn) { if(odw[miasto] || ile[miasto]<d)return; odw[miasto]=ozn; for (std::list<int>::iterator it=miasta[miasto].begin(); it!=miasta[miasto].end(); ++it) { scan(*it,ozn); } } int main(void) { int i; int a,b; int o; scanf("%d %d %d",&n,&m,&d); for(i=0;i<m;++i) { scanf("%d %d",&a,&b); //printf("%d %d\n",a ,b); miasta[a].push_back(b); miasta[b].push_back(a); ++ile[a]; ++ile[b]; } //for (std::list<int>::iterator it=miasta[2].begin(); it!=miasta[2].end(); ++it)std::cout << ' ' << *it; // printf("\n"); //lecimy po miastach for(i=1;i<=n;++i) { scan(i,i); o=odw[i]; if(o>0) { ++s[o]; if(max<s[o]) { max=s[o]; miast_max=o; } } //printf("i=%d ile=%d odw=%d\n",i, ile[i],odw[i]); } if(max<2) { printf("NIE\n"); return 0; } printf("%d\n",max); for(i=1;i<=n;++i) { if(odw[i]==miast_max) { printf("%d ",i); } //printf("i=%d ile=%d odw=%d\n",i, ile[i],odw[i]); } printf("\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 | #include <stdio.h> #include <list> #include <iostream> int n,m,d; std::list<int> miasta[200001]; int ile[200001]={0}; int odw[200001]={0}; int s[200001]={0}; int miast_max=-1; int max=0; void scan(int miasto, int ozn) { if(odw[miasto] || ile[miasto]<d)return; odw[miasto]=ozn; for (std::list<int>::iterator it=miasta[miasto].begin(); it!=miasta[miasto].end(); ++it) { scan(*it,ozn); } } int main(void) { int i; int a,b; int o; scanf("%d %d %d",&n,&m,&d); for(i=0;i<m;++i) { scanf("%d %d",&a,&b); //printf("%d %d\n",a ,b); miasta[a].push_back(b); miasta[b].push_back(a); ++ile[a]; ++ile[b]; } //for (std::list<int>::iterator it=miasta[2].begin(); it!=miasta[2].end(); ++it)std::cout << ' ' << *it; // printf("\n"); //lecimy po miastach for(i=1;i<=n;++i) { scan(i,i); o=odw[i]; if(o>0) { ++s[o]; if(max<s[o]) { max=s[o]; miast_max=o; } } //printf("i=%d ile=%d odw=%d\n",i, ile[i],odw[i]); } if(max<2) { printf("NIE\n"); return 0; } printf("%d\n",max); for(i=1;i<=n;++i) { if(odw[i]==miast_max) { printf("%d ",i); } //printf("i=%d ile=%d odw=%d\n",i, ile[i],odw[i]); } printf("\n"); return 0; } |