拓补排序

//输入形式是邻接矩阵 #include <iostream> #include <stack> using namespace std; class ArcNode { public: int adjvex; ArcNode *next; ArcNode() :next(NULL) {} }; class VNode { public: char data; ArcNode *first; VNode():first(new ArcNode()){} }; class Map { VNode *vertices; int vexnum; int arcnum; bool *final; int *indegree; bool TopologicalSort(int count); public: Map(int vnum,int **mx); bool TopologicalSort(); }; Map::Map(int vnum, int **mx) { vexnum = vnum; vertices = new VNode[vexnum]; for (int i = 0; i < vexnum; i++) { ArcNode *p = vertices[i].first; for (int j = 0; j < vexnum; j++) if (mx[i][j]) { p->adjvex = j; p->next = new ArcNode(); p = p->next; } } final = new bool[vexnum]; for (int i = 0; i < vexnum; i++) final[i] = false; } bool Map::TopologicalSort(int count) { indegree = new int[vexnum]; for (int i = 0; i < vexnum; i++) indegree[i] = 0; for (int i = 0; i < vexnum; i++) { for (int j = 0; j < vexnum; j++) { ArcNode *p = vertices[j].first; while (p->next) { if (p->adjvex > i) break; if (p->adjvex == i) indegree[i]++; p = p->next; } } } stack<int> s; for (int i = 0; i < vexnum; i++) if (!indegree[i] && !final[i]) { final[i] = true; s.push(i); cout << i << ' '; } while (!s.empty()) { int v = s.top(); s.pop(); count++; ArcNode *p = vertices[v].first; while (p->next) { indegree[p->adjvex]--; p = p->next; } for (int i = 0; i < vexnum; i++) if (!indegree[i] && !final[i]) { s.push(i); final[i] = true; cout << i << ' '; } } if (count < vexnum) return false; return true; } bool Map::TopologicalSort() { int count =0; cout << count << endl; if (TopologicalSort(count)) { cout << endl; return true; } cout << endl; return false; } int main() { int t; cin >> t; while (t--) { int vnum; cin >> vnum; int **mx = new int*[vnum]; for (int i = 0; i < vnum; i++) mx[i] = new int[vnum]; for (int i = 0; i < vnum; i++) for (int j = 0; j < vnum; j++) cin >> mx[i][j]; Map map(vnum, mx); if (map.TopologicalSort()) cout << "无圈图" << endl; else cout << "有圈图" << endl; for (int i = 0; i < vnum; i++) delete mx[i]; delete mx; } system("pause"); return 0; }