7-354 拓扑排序：寻找真正的首富 - C++代码实现

这篇文章详细介绍了如何使用拓扑排序算法来解决一个判断谁是真正首富的问题。文章通过构建一个有向图，并使用入度统计和队列来判断是否有唯一入度为0的节点，从而确定真正的首富。文中还提供了清晰的代码实现，方便读者理解和学习。\n\n## 问题描述\n\n有n个富豪，他们聚在一起想要知道谁才是他们之中的最有钱的人，然而他们所有人都隐藏了家产，根据调查，你知道了m个富豪之间的财富关系。现在你要根据已有的关系信息推理出这n个人之中谁才是真正的首富。\n\n## 输入格式\n\n多组输入。每组第一行输入2个整数n,m（0<=m，n<=1000000）,当n=m=0时结束输入。接下来m行，每行输入一个整数a(1<=a<=n)，一个字符c，和一个整数b(1<=b<=n)，表示编号为a的富豪与编号为b（a不等于b）的富豪的财富关系，关系只有两种：大于或是小于。保证输入关系无矛盾，如1>2，2>3，3>1这种情况是矛盾的。\n\n## 输出格式\n\n若能推理出谁是首富，则输出首富的编号，否则输出“no solution”。\n\n## 样例输入\n\n输入样例:\n在这里给出一组输入。例如：\n\n3 2\n1 > 3\n2 > 3\n3 2\n1 > 2\n2 > 3\n\n## 输出样例\n\n在这里给出相应的输出。例如：\n\nno solution\n1\n\n## 思路\n\n首先，我们可以使用拓扑排序的思想来解决这个问题。拓扑排序可以用来判断一个有向图是否有环，如果有环，则无法得到一个合理的排序。而在本题中，如果存在环，则无法推理出谁是真正的首富。\n\n具体的算法实现如下：\n1. 根据输入的财富关系，构建一个有向图。图的节点表示富豪的编号，边表示财富关系。如果a > b，则在a和b之间存在一条从a指向b的边。\n2. 统计每个节点的入度，即有多少条边指向该节点。入度为0的节点表示没有其他节点指向它，即没有财富关系的限制，可以认为是真正的首富。\n3. 如果有且仅有一个入度为0的节点，则输出该节点的编号作为真正的首富；否则输出"no solution"。\n\n## 代码实现\n\nc++\n#include <iostream>\n#include <vector>\n#include <queue>\nusing namespace std;\n\nint main() {\n int n, m;\n while (cin >> n >> m && n != 0 && m != 0) {\n vector<int> indegree(n + 1, 0); // 统计入度\n vector<vector<int>> graph(n + 1); // 存储有向图\n\n for (int i = 0; i < m; i++) {\n int a, b;\n char c;\n cin >> a >> c >> b;\n if (c == '>') {\n graph[a].push_back(b);\n indegree[b]++;\n } else {\n graph[b].push_back(a);\n indegree[a]++;\n }\n }\n\n queue<int> q;\n for (int i = 1; i <= n; i++) {\n if (indegree[i] == 0) {\n q.push(i);\n }\n }\n if (q.size() != 1) {\n cout << "no solution" << endl;\n } else {\n cout << q.front() << endl;\n }\n }\n return 0;\n}\n