竞赛图是一个有向图（有向图），通过为无向完全图中的每条边指定一个方向而获得也就是说，它是一个有向图，其中每对顶点由一条有向边连接。
数据结构为邻接矩阵。
如果图是竞赛图，那么算法是什么？
最佳答案
邻接矩阵中有n^2个条目，您需要所有条目中的信息来解决问题。（你需要1个来检查正确的边是否存在，而0个要检查后面的边是否不存在）因此，因为你必须从矩阵中读取至少N个2个条目，所以整个问题必须至少占用O（n ^ 2）的时间。
关于BFS搜索尝试：如果你的遍历取O（n^2）-由于需要在邻接矩阵中查找边，它将取O（n^2）-那么后边检查是否为常数时间并不重要，整个算法仍然是O（n^2）。
另一种看待这个问题的方法是：因为边的数目等于可能的顶点对的数目，所以会有n*（n-1）/2条边，即o（n^2）。你的遍历是o（v+e），因此是o（n+n^2），因此是o（n^2）。
由于此算法的最佳情况时间是o（n^2），您也可以简单地循环遍历矩阵的右上半部分（在对角线上方），并检查对于这些条目中的每一个，a）它是1，或者b）它的转置等效值是1。