文章
65
粉丝
19
获赞
367
访问
38.8k
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
未...
登录后发布评论
暂无评论,来抢沙发