华为8月16的机试第二题怎么做

就是求拓扑排序呀

//用弗洛伊德算法思想 #include <iostream> #include <string> #include <vector> #include <algorithm> #include <map> using namespace std; vector<int> label; vector<int> dataIndex; void AddDependency(unsigned int Moduled, unsigned int DeModuled) { for(int i = 0; i < label.size(); ++i) { if(Moduled == label[i]) { dataIndex.push_back(Moduled); break; } } for(int j = 0; j < label.size(); ++j) { if(DeModuled == label[j]) { dataIndex.push_back(DeModuled); break; } } } int main() { vector<string> input; vector<int> result; string temp; while(getline(cin, temp)) { input.push_back(temp); } int len = input.size(); for(int i = 0; i < len; i++) { temp = input[i]; int k = 3; int num = 0; while(temp[k] != ',') { if(temp[k] >= '0' && temp[k] <= '9') { num = num * 16 + temp[k] - '0'; k++; } else { num = num * 16 + temp[k] - 'a'; k++; } } result.push_back(num); num = 0; k = k + 4; while(temp[k] != '}') { if(temp[k] >= '0' && temp[k] <= '9') { num = num * 16 + temp[k] - '0'; k++; } else { num = num * 16 + temp[k] - 'a'; k++; } } result.push_back(num); num = 0; } /* vector<int> time; vector<int> duitime; map<int, int> Hash; for(int i = 0; i < result.size()-1; i += 2) { ++Hash[result[i+1]]; } map<int, int>::iterator mapi; for(mapi = Hash.begin(); mapi != Hash.end(); mapi++) { int a = mapi->first; int b = mapi->second; duitime.push_back(a); time.push_back(b); } */ vector<int> result_temp(result); sort(result_temp.begin(), result_temp.end()); label.push_back(result_temp[0]); for(int i = 1; i < result_temp.size(); i++) { if(result_temp[i] != result_temp[i-1]) label.push_back(result_temp[i]); } /* for(int i = 0; i < label.size(); i++) cout << label[i] << endl << endl; */ for(int i = 0; i < result.size()-1; i += 2) { AddDependency(result[i], result[i+1]); } /* for(int i = 0; i < dataIndex.size(); i++) cout << dataIndex[i] << endl; */ int **arr = new int*[label.size()]; for(int i = 0; i < label.size(); i++) arr[i] = new int[label.size()]; //初始化数组为全0； for(int i = 0; i < label.size(); i++) for(int j = 0; j < label.size(); j++) arr[i][j] = 0; for(int i = 0; i < result.size()-1; i += 2) { arr[dataIndex[i]-1][dataIndex[i+1]-1] = 1; } /* for(int i = 0; i < label.size(); i++) { for(int j = 0; j < label.size(); j++) cout << arr[i][j] << ' '; cout << endl; } cout << endl; */ for(int i = 0; i < label.size(); i++) { for(int j = 0; j < label.size(); j++) { for(int k = 0; k < label.size(); k++) { if(arr[j][i] == 1 && arr[i][k] == 1) { arr[j][k] = 1; } } } } /* for(int i = 0; i < label.size(); i++) { for(int j = 0; j < label.size(); j++) cout << arr[i][j] << ' '; cout << endl; } cout << endl; */ //输出的格式没有调 for(int i = 0; i < label.size(); ++i) { if(arr[i][i] == 1) cout << label[i] << endl; } //最后需要释放内存 return 0; }