【正确答案】正确答案：基本设计思想：若存在这样的顶点，该顶点到其他任一结点都有一条有向路，又因为该有向图是无环路的，那么该顶点到这些结点之间的路构成一棵树，此树上的结点数应该等于该图的结点数。若不等于（小于），则不存在这样的结点。因此，从任意结点开始，遍历此图（深度优先或者是广度优先均可），若visited的结点数等于图的结点数，则存在，否则不存在。结点和邻接表定义如下：struct node{ int adjvex； node *next；}；//结点的定义struct g{ vertexttype data； node *firstarc；Jtypedef g ADJLIST；//邻接表的定义

【正确答案】正确答案：算法实现如下： 方法一：广度优先遍历（使用队列） int rbfs (ADJLIST g，int vi) int i， count， yes； yes=0； courit=1； queue Q； for（int i=O；i＜n，i++）visited[i]=0；11初始化访问标记数组 enqueue (vi，Q) ； visited [vi]=1； //初始化 while (!empty {Q) && ! yes) { int w—Q.front； p=g[w]. firstarc； while (p!=NULL&&!yes) { w=p—＞adjdata； if (visited [w] =0) { visited [w] =1； enqueue (w， Q) ； } else p=p—＞next； }

【正确答案】正确答案：时间复杂度分析：无论是采用深度优先遍历还是广度优先遍历，可知每个结点均访问了一次，因此时间复杂度为O(n)。