文章
74
粉丝
0
获赞
0
访问
8.7k
(1)算法思想:对于唯一的拓扑序列,每一次进行扫描的时候,只有一个节点的入度是0,如果有多个节点的入度是0,那么就表明该拓扑序列不是唯一的。
(2)代码:
int uniquely(MGraph G){
int n = G.numVertices;
int countin=0;//用于记录已经消除的节点数量,每一轮都要提出一个节点
for(int m=0;m<n;m++){//最多有n个节点,那么就表示要进行n次去边,因为拓扑序列唯一
int count = 0;
for(int i=0;i<n;i++){
int degreein=0;//用于记录入度
for(int j=0;j<n;j++){
degreein+=Edge[j][i];
}
if(degreein == 0){
count++;
int start=i;//将i作为开始的节点提出并将边全部去除
}
}
countin++;
if(count-countin != 1) return 0;//存在节点的入度0的个数不为1,直接返回0
for(int s=0;s<n;s++){
Edge[start][s]=0;//将边全部去掉然后开始新的一轮扫描
}
}
return 1;
}
评分及理由
(1)得分及理由(满分4分)
得分:4分
理由:学生的算法思想描述准确,明确指出拓扑序列唯一的条件是每一步只有一个入度为0的节点。这与标准答案的核心思想一致,表述清晰完整。
(2)得分及理由(满分9分)
得分:3分
理由:代码存在多处逻辑错误:
1. 未正确维护入度数组,而是每次重新计算入度,效率低下且逻辑错误(扣3分)
2. 变量start的作用域问题,在if语句内定义但在外部使用(扣1分)
3. 边删除逻辑错误,只删除了一个...
登录后发布评论
暂无评论,来抢沙发