文章
132
粉丝
19
获赞
402
访问
60.9k
 
1.不停遍历寻找入度为0的点,将其存入队列,队列里如果出现了两个点及以上说明不唯一,因为可以选择任意一个先出队,有多个拓扑序列,返回0即可
2.
int uniquely(MGraph G){
	char[MAXV] ver = G.verticesList;
	int graph[MAXV][MAXV] = G.Edge;
	int nv = G.numsVertices;
	int ne = G.numEdges;
	queue<int> q;
	vector<int> in; // 入度个数
	for(int i=0;i<nv;i++){
		for(int j=0;j<nv;j++){
			if(graph[i][j]==1){
				in[j]++;
			}
		}
	}
	//找到入度为0的点
	for(int i=0;i<nv;i++){
		if(in[i]==0){
			q.push(i);
		}
	}
	if(q.empty()){
		return 0;//没有拓扑排序
	}
	while(!q.empty()){
		if(q.size()>=2){
			return 0;
		}
		int temp = q.front();
		q.pop();
		for(int i=0;i<nv;i++){
			if(graph[temp][i]==1){
				in[i]--;
			}
			if(in[i]==0){
				q.push(i);
			}
		}
	}
	return 1;
}
评分及理由
(1)得分及理由(满分4分)
得分:4分
理由:学生的设计思想与标准答案一致,正确地描述了通过队列寻找入度为0的顶点,并判断是否存在多个入度为0的顶点来确定拓扑序列的唯一性。思路清晰且正确。
(2)得分及理由(满分9分)
得分:7分
理由:代码整体逻辑正确,但存在以下问题:
G.numsVertices应为G.numVertices,扣1分。in未...
登录后发布评论
暂无评论,来抢沙发