#include <iostream> #include <vector> using namespace std; int longestPath = 0, longestId = 0; vector < vector <bool> > sasiedziKwadrat; vector < vector <int> > sasiedziLista; void DFS(int start, vector <int> path, int leng) { path.push_back(start); leng++; if(sasiedziLista[start].size() == 0) { if(leng > longestPath) { //cout << "x " << endl; //for(int i = 0; i < path.size(); i++) //{ // cout << path[i] << " "; //} //cout << endl; longestPath = leng; longestId = path[(leng - 1) / 2]; //cout << ">> " << longestId << endl; } } else { for(int i = 0; i < sasiedziLista[start].size(); i++) { //cout << "-> " << sasiedziLista[start][i] << " " << leng << endl; DFS(sasiedziLista[start][i], path, leng); } } } int main() { vector <int> starterzy; vector <int> pat; int ileUmiejetnosci, ileZaleznosci, ileUsunac, a, b; bool isOk; cin >> ileUmiejetnosci >> ileZaleznosci >> ileUsunac; for(int i = 0; i < ileUmiejetnosci; i++) { sasiedziKwadrat.push_back(vector <bool>()); sasiedziLista.push_back(vector <int>()); for(int j = 0; j < ileUmiejetnosci; j++) { sasiedziKwadrat[i].push_back(0); } } for(int i = 0; i < ileZaleznosci; i++) { cin >> a >> b; sasiedziKwadrat[a - 1][b - 1] = true; sasiedziLista[a - 1].push_back(b - 1); } for(int z = 0; z < ileUsunac; z++) { starterzy.clear(); longestPath = 0; for(int i = 0; i < ileUmiejetnosci; i++) { isOk = true; for(int j = 0; j < ileUmiejetnosci; j++) { if(sasiedziKwadrat[j][i] == true) { isOk = false; break; } } if(isOk == true) { starterzy.push_back(i); } } for(int i = 0; i < starterzy.size(); i++) { DFS(starterzy[i], pat, 0); } for(int i = 0; i < sasiedziLista[longestId].size(); i++) { sasiedziKwadrat[longestId][sasiedziLista[longestId][i]] = false; } sasiedziLista[longestId].clear(); for(int i = 0; i < ileUmiejetnosci; i++) { for(int j = 0; j < sasiedziLista[i].size(); j++) { if(sasiedziLista[i][j] == longestId) { //cout << "<< " << sasiedziLista[i][j] << endl; sasiedziLista[i].erase(sasiedziLista[i].begin() + j); break; } } } } starterzy.clear(); longestPath = 0; for(int i = 0; i < ileUmiejetnosci; i++) { isOk = true; for(int j = 0; j < ileUmiejetnosci; j++) { if(sasiedziKwadrat[j][i] == true) { isOk = false; break; } } if(isOk == true) { starterzy.push_back(i); } } //cout << "there" << endl; for(int i = 0; i < starterzy.size(); i++) { DFS(starterzy[i], pat, 0); } if(ileUsunac >= ileUmiejetnosci) { cout << 0 << endl; } else { cout << longestPath << endl; } /*for(int i = 0; i < ileUmiejetnosci; i++) { cout << i << " > "; for(int j = 0; j < ileUmiejetnosci; j++) { cout << sasiedziKwadrat[i][j] << " "; } cout << endl; } cout << endl; for(int i = 0; i < ileUmiejetnosci; i++) { cout << i << " > "; for(int j = 0; j < sasiedziLista[i].size(); j++) { cout << sasiedziLista[i][j] << " "; } cout << endl; }*/ 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 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 | #include <iostream> #include <vector> using namespace std; int longestPath = 0, longestId = 0; vector < vector <bool> > sasiedziKwadrat; vector < vector <int> > sasiedziLista; void DFS(int start, vector <int> path, int leng) { path.push_back(start); leng++; if(sasiedziLista[start].size() == 0) { if(leng > longestPath) { //cout << "x " << endl; //for(int i = 0; i < path.size(); i++) //{ // cout << path[i] << " "; //} //cout << endl; longestPath = leng; longestId = path[(leng - 1) / 2]; //cout << ">> " << longestId << endl; } } else { for(int i = 0; i < sasiedziLista[start].size(); i++) { //cout << "-> " << sasiedziLista[start][i] << " " << leng << endl; DFS(sasiedziLista[start][i], path, leng); } } } int main() { vector <int> starterzy; vector <int> pat; int ileUmiejetnosci, ileZaleznosci, ileUsunac, a, b; bool isOk; cin >> ileUmiejetnosci >> ileZaleznosci >> ileUsunac; for(int i = 0; i < ileUmiejetnosci; i++) { sasiedziKwadrat.push_back(vector <bool>()); sasiedziLista.push_back(vector <int>()); for(int j = 0; j < ileUmiejetnosci; j++) { sasiedziKwadrat[i].push_back(0); } } for(int i = 0; i < ileZaleznosci; i++) { cin >> a >> b; sasiedziKwadrat[a - 1][b - 1] = true; sasiedziLista[a - 1].push_back(b - 1); } for(int z = 0; z < ileUsunac; z++) { starterzy.clear(); longestPath = 0; for(int i = 0; i < ileUmiejetnosci; i++) { isOk = true; for(int j = 0; j < ileUmiejetnosci; j++) { if(sasiedziKwadrat[j][i] == true) { isOk = false; break; } } if(isOk == true) { starterzy.push_back(i); } } for(int i = 0; i < starterzy.size(); i++) { DFS(starterzy[i], pat, 0); } for(int i = 0; i < sasiedziLista[longestId].size(); i++) { sasiedziKwadrat[longestId][sasiedziLista[longestId][i]] = false; } sasiedziLista[longestId].clear(); for(int i = 0; i < ileUmiejetnosci; i++) { for(int j = 0; j < sasiedziLista[i].size(); j++) { if(sasiedziLista[i][j] == longestId) { //cout << "<< " << sasiedziLista[i][j] << endl; sasiedziLista[i].erase(sasiedziLista[i].begin() + j); break; } } } } starterzy.clear(); longestPath = 0; for(int i = 0; i < ileUmiejetnosci; i++) { isOk = true; for(int j = 0; j < ileUmiejetnosci; j++) { if(sasiedziKwadrat[j][i] == true) { isOk = false; break; } } if(isOk == true) { starterzy.push_back(i); } } //cout << "there" << endl; for(int i = 0; i < starterzy.size(); i++) { DFS(starterzy[i], pat, 0); } if(ileUsunac >= ileUmiejetnosci) { cout << 0 << endl; } else { cout << longestPath << endl; } /*for(int i = 0; i < ileUmiejetnosci; i++) { cout << i << " > "; for(int j = 0; j < ileUmiejetnosci; j++) { cout << sasiedziKwadrat[i][j] << " "; } cout << endl; } cout << endl; for(int i = 0; i < ileUmiejetnosci; i++) { cout << i << " > "; for(int j = 0; j < sasiedziLista[i].size(); j++) { cout << sasiedziLista[i][j] << " "; } cout << endl; }*/ return 0; } |