#include <iostream> #include <queue> #include <list> using namespace std; queue<int> do_usuniecia; int *odwiedzone; list<int> * krawedzie; int * ile; int dfs(int w, int id){ odwiedzone[w]=id; int licznik=0; for(list<int>::iterator it=krawedzie[w].begin(); it!=krawedzie[w].end(); it++){ if(odwiedzone[*it]==0&&ile[*it]!=0){ licznik++; licznik+=dfs(*it, id); } } return licznik; } int main() { ios_base::sync_with_stdio(false); int n, m, d; cin >> n >> m >> d; queue<int> do_usuniecia; krawedzie = new list<int>[n]; ile = new int[n]; for(int i=0; i<n; i++)ile[i]=0; int a, b; while(m--){ cin >> a >> b; krawedzie[a-1].push_back(b-1); krawedzie[b-1].push_back(a-1); ile[a-1]++; ile[b-1]++; } for(int i=0; i<n; i++){ if(ile[i]<d)do_usuniecia.push(i); } while(!do_usuniecia.empty()){ while(!krawedzie[do_usuniecia.front()].empty()){ if(ile[ krawedzie [ do_usuniecia.front() ] .front() ]){ ile[krawedzie[do_usuniecia.front()].front()]--; if(ile[krawedzie[do_usuniecia.front()].front()]<d) do_usuniecia.push(krawedzie[do_usuniecia.front()].front()); } krawedzie[do_usuniecia.front()].pop_front(); } ile[do_usuniecia.front()]=0; do_usuniecia.pop(); } /*list<int>::iterator it2; for(int i=0; i<n; i++){ if(ile[i]!=0){ for(list<int>::iterator it = krawedzie[i].begin(); it!=krawedzie[i].end(); it++){ if(ile[*it]==0){ it2=it; it++; krawedzie[i].erase(it2); it--; } } } }*/ int max, wynik, id, maxid=0; id=1; max=0; odwiedzone = new int[n]; for(int i=0; i<n; i++) odwiedzone[i]=false; for(int i=0; i<n; i++){ if(ile[i]&&odwiedzone[i]==0){ wynik=dfs(i, id)+1; if(wynik>=max){ max=wynik; maxid=id; } id++; } } if(max){ cout << max << endl; for(int i=0; i<n; i++){ if(odwiedzone[i]==maxid) cout << i+1 << " "; } } else cout << "NIE"; 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 90 91 92 93 | #include <iostream> #include <queue> #include <list> using namespace std; queue<int> do_usuniecia; int *odwiedzone; list<int> * krawedzie; int * ile; int dfs(int w, int id){ odwiedzone[w]=id; int licznik=0; for(list<int>::iterator it=krawedzie[w].begin(); it!=krawedzie[w].end(); it++){ if(odwiedzone[*it]==0&&ile[*it]!=0){ licznik++; licznik+=dfs(*it, id); } } return licznik; } int main() { ios_base::sync_with_stdio(false); int n, m, d; cin >> n >> m >> d; queue<int> do_usuniecia; krawedzie = new list<int>[n]; ile = new int[n]; for(int i=0; i<n; i++)ile[i]=0; int a, b; while(m--){ cin >> a >> b; krawedzie[a-1].push_back(b-1); krawedzie[b-1].push_back(a-1); ile[a-1]++; ile[b-1]++; } for(int i=0; i<n; i++){ if(ile[i]<d)do_usuniecia.push(i); } while(!do_usuniecia.empty()){ while(!krawedzie[do_usuniecia.front()].empty()){ if(ile[ krawedzie [ do_usuniecia.front() ] .front() ]){ ile[krawedzie[do_usuniecia.front()].front()]--; if(ile[krawedzie[do_usuniecia.front()].front()]<d) do_usuniecia.push(krawedzie[do_usuniecia.front()].front()); } krawedzie[do_usuniecia.front()].pop_front(); } ile[do_usuniecia.front()]=0; do_usuniecia.pop(); } /*list<int>::iterator it2; for(int i=0; i<n; i++){ if(ile[i]!=0){ for(list<int>::iterator it = krawedzie[i].begin(); it!=krawedzie[i].end(); it++){ if(ile[*it]==0){ it2=it; it++; krawedzie[i].erase(it2); it--; } } } }*/ int max, wynik, id, maxid=0; id=1; max=0; odwiedzone = new int[n]; for(int i=0; i<n; i++) odwiedzone[i]=false; for(int i=0; i<n; i++){ if(ile[i]&&odwiedzone[i]==0){ wynik=dfs(i, id)+1; if(wynik>=max){ max=wynik; maxid=id; } id++; } } if(max){ cout << max << endl; for(int i=0; i<n; i++){ if(odwiedzone[i]==maxid) cout << i+1 << " "; } } else cout << "NIE"; return 0; } |