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

【正确答案】算法实现如下： 方法一：广度优先遍历(使用队列) int rbfs(ADJLIST g,int vi) { int i,count,yes; yes=0; count=1; queue Q; for(int i=0;i＜n;i++)visited[i]=0;//初始化访问标记数组 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; count++; enqueue(W,Q); } else p=p-＞next; } } if(count==n)//n为该有向图中结点的总数 yes=1; return yes; } 方法二：深度优先遍历(使用栈) int rdfs(ADJLIST g,int vi) { int i,count,yes; yes=0; count=1; stack s; for(int i=0;i＜n;i++)visited[i]=0;//初始化访问标记数组 push(vi,s); visited[vi]=1;//初始化 while(!empty(s)&&yes==0) { int w=top(s); p=g[w].firstarc; while(p!=NULL&&visited[p-＞adjdata]) { p=p-＞next; if(p==NULL)pop(s); elSe { w=p-＞adjdata; visited[w]=1; count++; push(w,s); } } } if(count==n)//n为该有向图中的结点数 yes=1; return yes; {

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