上学期学了数据结构, 但是总是掌握不牢固, 这学期的算法课给了这样一道 OJ 题目
描述:
There is a group of people playing table tennis, each person can only play with the others once.
The rules of the game are as follows:
If A beats B, and B beats C, and there is no competition between A and C, then A beats C.
If A beats B, B beats C, and C beats A, then no one is champion.
Your task is to figure out whether there is a champion.
Input
Each test case contains several groups. One group begins with an integer n(n<1000), followed by n lines. Each line has a pair of names (separated by space), which means the first one beats the second one. If n is 0, the input ends.
- Output
- If there is a winner, print "Yes", else print "No".
示例测试集:
- 第 1 组
输入:
- 2
- qRj dIm
- aTy oFu
- 4
- qRj aTy
- qRj oFu
- oFu cLq
- aTy qUr
- 0
输出:
No
Yes
这道题明显是用图论的知识, 我的解题思路如下, 通过每次输入构建一个有向图, 然后通过判断
1. 图中入度为 0 的顶点, 当且仅当存在一个入度为 0 的顶点才可能有 winner
2. 图是否有环, 如果存在环, 则肯定不可能有 winner
3. 个人认为第二点太过绝对, 例如 a b b c c d d a 我觉得这组数据中是有胜利者 d 的但是通过试验, 测试点中并没有考虑这种情况, 故我也不考虑了
具体代码如下
- #include <iostream>
- #include<string>
- #include<stack>
- #define MAXVERTEX 10000 // 最大顶点数
- using namespace std;
- int indegree[MAXVERTEX];
- typedef string vertextype; // 定义顶点的存储类型
- typedef struct ArcNode // 边表节点
- {
- int adjvex; // 邻接点域, 存储该顶点对应的下标
- struct ArcNode *next; // 链域, 指向下一个邻接点
- }ArcNode;
- typedef struct VertexNode // 顶点表节点
- {
- vertextype data; // 存储顶点数据的信息
- ArcNode *firstarc; // 边表头指针
- }AdjList[MAXVERTEX];
- typedef struct
- {
- AdjList adjlist; // 定义邻接表
- int numvertex; // 当前邻接表的顶点数
- int numarc; // 当前邻接表的边数
- }GraphAdjList;
- // 判断 x 是不是 G 中的节点
- bool ExitInGraph(GraphAdjList &G, VertexNode x) {
- for (int i = 0; i <G.numvertex; i++) {
- if (G.adjlist[i].data == x.data)
- return true;
- }
- return false;
- }
- // 把 G 中节点 x,y 连接起来
- void Connect(GraphAdjList &G, VertexNode x, VertexNode y) {
- int xindex, yindex;
- for (int i = 0; i < G.numvertex; i++) {
- if (G.adjlist[i].data == y.data)
- yindex = i;
- if (G.adjlist[i].data == x.data)
- xindex = i;
- }
- ArcNode *e = new ArcNode;
- e->adjvex = yindex;
- e->next = G.adjlist[xindex].firstarc;
- G.adjlist[xindex].firstarc = e;
- }
- // 寻找当前节点在 G 中的 index
- int FindeIndex(GraphAdjList &G, VertexNode x) {
- int xindex;
- for (int i = 0; i <G.numvertex; i++) {
- if (G.adjlist[i].data == x.data)
- return i;
- }
- }
- // 建立图的邻接表
- void CreateAdjListGraph(GraphAdjList &G, int num)
- {
- ArcNode *e;
- G.numarc = num; // 输入当前图的边数
- G.numvertex = 0; // 初始图的节点数为 0
- for (int i = 0, j = 0; i < G.numarc; i++) // 建立顶点表, j 用来表示当前头结点的 index
- {
- string a, b;
- cin>> a>> b;
- VertexNode x, y;
- x.data = a, y.data = b;
- if (ExitInGraph(G, x) && ExitInGraph(G, y)) {
- Connect(G, x, y);
- }
- else if (!ExitInGraph(G, x) && ExitInGraph(G, y)) {
- e = new ArcNode;
- G.adjlist[j].data = x.data; // 给当前节点赋值 data
- e->adjvex = FindeIndex(G, y); // 给 e 赋值
- e->next = NULL;
- G.adjlist[j].firstarc = e;
- j++;
- G.numvertex++;
- }
- else if (ExitInGraph(G, x) && !ExitInGraph(G, y)) {
- e = new ArcNode;
- G.adjlist[j].data = y.data;
- G.adjlist[j].firstarc = NULL;
- e->adjvex = j;
- int xindex = FindeIndex(G, x);
- e->next = G.adjlist[xindex].firstarc;
- G.adjlist[xindex].firstarc = e;
- j++;
- G.numvertex++;
- }
- else {
- e = new ArcNode;
- G.adjlist[j].data = x.data;
- G.adjlist[++j].data = y.data;
- G.adjlist[j].firstarc = NULL;
- e->adjvex = j;
- e->next = NULL;
- G.adjlist[j - 1].firstarc = e;
- G.numvertex += 2;
- j++;
- }
- }
- }
- void FindInDegree(GraphAdjList &g, int indegree[])
- { // 求每个顶点的入度
- int i;
- ArcNode *p;
- for (i = 0; i<g.numvertex; i++)
- indegree[i] = 0;
- for (i = 0; i<g.numvertex; i++)
- {
- p = g.adjlist[i].firstarc;
- while (p)
- {
- indegree[p->adjvex]++;
- p = p->next;
- }
- }
- }
- bool TopologicalSort(GraphAdjList &g) // 判断图中是否存在回路 存在 返回 true
- {
- for (int i = 0; i<g.numvertex; i++)
- indegree[i] = 0;
- int count;
- int k, i;
- ArcNode *p;
- stack<int>s;
- FindInDegree(g, indegree); // 对各顶点求入度
- for (i = 0; i<g.numvertex; i++) // 将入度为 0 的顶点压入栈
- if (!indegree[i])
- {
- s.push(i);
- //visited[i] = 1;
- }
- //if (s.size() != 1)return true;// 不能拥有两个入读为 0 的点
- count = 0;
- while (!s.empty())
- {
- i = s.top();
- s.pop();
- cout<<g.adjlist[i].data <<" "; // 输出拓扑排序序列
- count++;
- for (p = g.adjlist[i].firstarc; p; p = p->next)
- {
- k = p->adjvex;
- //visited[k] = 1;
- if (!(--indegree[k]))
- s.push(k);
- }
- }
- if ((count == g.numvertex))
- {
- return false;// 这就说明没有环
- }
- else
- return true;
- //printf("\n 该图有回路 \ n");
- }
- int main()
- {
- int n;
- while (cin>> n, n) {
- GraphAdjList G;
- CreateAdjListGraph(G, n);
- if (TopologicalSort(G))
- cout << "No" << endl;
- else
- cout << "Yes" << endl;
- n = 0;
- }
- //system("pause");
- return 0;
- }
代码不完善, 还请多多原谅
来源: http://www.bubuko.com/infodetail-2996434.html