#include <iostream> #include <algorithm> #include <vector> using namespace std; vector< vector < int > > roadsFromCity(200001); vector<int> roadsNumber(200001); vector<int> subgraphNum(200001); vector<bool> removed(200001); int n, m, d; int groupNum; bool DFS(int); void DFSErase(int); int main() { for(int i = 0 ; i <= 200000; i++) { roadsNumber[i] = 0; subgraphNum[i] = 0; removed[i] = false; } //wczytywanie danych int city1, city2; cin >> n >> m >> d; for(int i = 0 ; i < m ; i ++) { cin >> city1 >> city2; roadsFromCity[city1].push_back(city2); roadsFromCity[city2].push_back(city1); } //usuwanie miast o mniej niż d drogach for(int i = 1; i <= n; i++) { roadsNumber[i] = roadsFromCity[i].size() ; } for(int i = 1; i <= n; i++) { DFSErase(i); } groupNum = 1; //szukanie wiekszego podgrafu conajmniej d stopnia for(int i = 1; i <= n ; i++) { if(subgraphNum[i] == 0) { if(DFS(i)) // zbuduj spojne podgrafy groupNum++; } } if(groupNum == 1) // brak miast cout << "NIE" << endl; else { vector<int> groupQuantity(groupNum); for (int i = 1; i <= n ; i++) // zlicz ilosc wierzcholkow w spojnych podgrafach { groupQuantity[subgraphNum[i]] ++; } int maxGroup = 1; for(unsigned int i = 1; i < groupQuantity.size(); i++) { if(groupQuantity[maxGroup] < groupQuantity[i]) maxGroup = i; } cout << groupQuantity[maxGroup] << endl; for(int i = 1; i <= n ; i++) { if(subgraphNum[i] == maxGroup) { cout << i << " "; } } cout << endl; } return 0; } bool DFS(int edgeNum) { if(roadsNumber[edgeNum] < d) { return false; } subgraphNum[edgeNum] = groupNum; for(unsigned int i = 0; i < roadsFromCity[edgeNum].size(); i++) { if(subgraphNum[roadsFromCity[edgeNum][i]] != groupNum) DFS(roadsFromCity[edgeNum][i]); } return true; } void DFSErase(int edgeNum) { if(roadsNumber[edgeNum] < d && removed[edgeNum] == false) { removed[edgeNum] = true; for(unsigned int j = 0 ; j < roadsFromCity[edgeNum].size(); j++) { roadsNumber[roadsFromCity[edgeNum][j]]--; DFSErase(roadsFromCity[edgeNum][j]); } } }
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 94 95 96 97 98 99 100 101 102 103 104 105 106 107 | #include <iostream> #include <algorithm> #include <vector> using namespace std; vector< vector < int > > roadsFromCity(200001); vector<int> roadsNumber(200001); vector<int> subgraphNum(200001); vector<bool> removed(200001); int n, m, d; int groupNum; bool DFS(int); void DFSErase(int); int main() { for(int i = 0 ; i <= 200000; i++) { roadsNumber[i] = 0; subgraphNum[i] = 0; removed[i] = false; } //wczytywanie danych int city1, city2; cin >> n >> m >> d; for(int i = 0 ; i < m ; i ++) { cin >> city1 >> city2; roadsFromCity[city1].push_back(city2); roadsFromCity[city2].push_back(city1); } //usuwanie miast o mniej niż d drogach for(int i = 1; i <= n; i++) { roadsNumber[i] = roadsFromCity[i].size() ; } for(int i = 1; i <= n; i++) { DFSErase(i); } groupNum = 1; //szukanie wiekszego podgrafu conajmniej d stopnia for(int i = 1; i <= n ; i++) { if(subgraphNum[i] == 0) { if(DFS(i)) // zbuduj spojne podgrafy groupNum++; } } if(groupNum == 1) // brak miast cout << "NIE" << endl; else { vector<int> groupQuantity(groupNum); for (int i = 1; i <= n ; i++) // zlicz ilosc wierzcholkow w spojnych podgrafach { groupQuantity[subgraphNum[i]] ++; } int maxGroup = 1; for(unsigned int i = 1; i < groupQuantity.size(); i++) { if(groupQuantity[maxGroup] < groupQuantity[i]) maxGroup = i; } cout << groupQuantity[maxGroup] << endl; for(int i = 1; i <= n ; i++) { if(subgraphNum[i] == maxGroup) { cout << i << " "; } } cout << endl; } return 0; } bool DFS(int edgeNum) { if(roadsNumber[edgeNum] < d) { return false; } subgraphNum[edgeNum] = groupNum; for(unsigned int i = 0; i < roadsFromCity[edgeNum].size(); i++) { if(subgraphNum[roadsFromCity[edgeNum][i]] != groupNum) DFS(roadsFromCity[edgeNum][i]); } return true; } void DFSErase(int edgeNum) { if(roadsNumber[edgeNum] < d && removed[edgeNum] == false) { removed[edgeNum] = true; for(unsigned int j = 0 ; j < roadsFromCity[edgeNum].size(); j++) { roadsNumber[roadsFromCity[edgeNum][j]]--; DFSErase(roadsFromCity[edgeNum][j]); } } } |