#include <cstdio> #include <algorithm> #include <vector> #include <queue> std::vector<int> v1[200005], v2[200005], wyn[200005]; std::queue<int> q; int n, maks, maksp, m, d, a, b, pol[200005], odw[200005], wyj[200005]; void bfs(int x){ q.push(x); for( int i=1; i<=n; i++ ) odw[i]=0; while( !q.empty() ){ int pocz=q.front(); q.pop(); if( odw[pocz] ) continue; odw[pocz]=1; wyn[x].push_back(pocz); for( std::vector<int>::iterator it=v2[pocz].begin(); it!=v2[pocz].end() ; it++ ){ if( !odw[*it] ){ q.push(*it); } } } } int main(){ scanf("%d%d%d", &n, &m, &d); for( int i=1; i<=m; i++ ){ scanf("%d%d", &a, &b); v1[a].push_back(b); v1[b].push_back(a); pol[a]++; pol[b]++; } for( int i=1; i<=n; i++ ){ if( v1[i].size()>0 && v1[i].size()<d ) q.push(i); } while( !q.empty() ){ int pocz=q.front(); q.pop(); if( wyj[pocz] ) continue; wyj[pocz]=1; for( std::vector<int>::iterator it=v1[pocz].begin(); it!=v1[pocz].end() ; it++ ){ if( !wyj[*it] ){ pol[*it]--; if( pol[*it]<d ){ q.push(*it); } } } } for( int i=1; i<=n; i++ ) if( !wyj[i] ) for( std::vector<int>::iterator it=v1[i].begin(); it!=v1[i].end(); it++ ) if( !wyj[*it] ) v2[i].push_back(*it); /* for( int i=1; i<=n; i++ ){ printf("%d: ", i); for( std::vector<int>::iterator it=v2[i].begin(); it!=v2[i].end(); it++ ) printf("%d, ", *it); printf(";\n"); }*/ for( int i=1; i<=n; i++ ){ if( !odw[i] && v2[i].size()>0 ){ bfs(i); } } for( int i=1; i<=n; i++ ){ if( wyn[i].size()>maks ){ maks=wyn[i].size(); maksp=i; } } if( maks==0 ){ printf("NIE\n"); return 0; } std::sort( wyn[maksp].begin(), wyn[maksp].end() ); printf("%d\n", maks); for( std::vector<int>::iterator it=wyn[maksp].begin(); it!=wyn[maksp].end(); it++ ) printf("%d ", *it); printf("\n"); }
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 | #include <cstdio> #include <algorithm> #include <vector> #include <queue> std::vector<int> v1[200005], v2[200005], wyn[200005]; std::queue<int> q; int n, maks, maksp, m, d, a, b, pol[200005], odw[200005], wyj[200005]; void bfs(int x){ q.push(x); for( int i=1; i<=n; i++ ) odw[i]=0; while( !q.empty() ){ int pocz=q.front(); q.pop(); if( odw[pocz] ) continue; odw[pocz]=1; wyn[x].push_back(pocz); for( std::vector<int>::iterator it=v2[pocz].begin(); it!=v2[pocz].end() ; it++ ){ if( !odw[*it] ){ q.push(*it); } } } } int main(){ scanf("%d%d%d", &n, &m, &d); for( int i=1; i<=m; i++ ){ scanf("%d%d", &a, &b); v1[a].push_back(b); v1[b].push_back(a); pol[a]++; pol[b]++; } for( int i=1; i<=n; i++ ){ if( v1[i].size()>0 && v1[i].size()<d ) q.push(i); } while( !q.empty() ){ int pocz=q.front(); q.pop(); if( wyj[pocz] ) continue; wyj[pocz]=1; for( std::vector<int>::iterator it=v1[pocz].begin(); it!=v1[pocz].end() ; it++ ){ if( !wyj[*it] ){ pol[*it]--; if( pol[*it]<d ){ q.push(*it); } } } } for( int i=1; i<=n; i++ ) if( !wyj[i] ) for( std::vector<int>::iterator it=v1[i].begin(); it!=v1[i].end(); it++ ) if( !wyj[*it] ) v2[i].push_back(*it); /* for( int i=1; i<=n; i++ ){ printf("%d: ", i); for( std::vector<int>::iterator it=v2[i].begin(); it!=v2[i].end(); it++ ) printf("%d, ", *it); printf(";\n"); }*/ for( int i=1; i<=n; i++ ){ if( !odw[i] && v2[i].size()>0 ){ bfs(i); } } for( int i=1; i<=n; i++ ){ if( wyn[i].size()>maks ){ maks=wyn[i].size(); maksp=i; } } if( maks==0 ){ printf("NIE\n"); return 0; } std::sort( wyn[maksp].begin(), wyn[maksp].end() ); printf("%d\n", maks); for( std::vector<int>::iterator it=wyn[maksp].begin(); it!=wyn[maksp].end(); it++ ) printf("%d ", *it); printf("\n"); } |