算法设计吧 关注:332贴子:101
  • 1回复贴,共1

拓扑排序及有向图圈的判定以及输出,考虑自环,不联通,重边

只看楼主收藏回复

我这段代码一般情况都能输出正确结果,但是上传作业时它内部显示运行错误(数组越界,指针,访问到不能访问到的内存区域等等)求大神们帮我看一下到底是身份问题?
#include<iostream>
using namespace std;
int circle(int *c,int (*a)[2],int m,int da){//圈的递归函数
int n = 0;
for (int i = 0; i < m; i++)
if (c[da] == a[i][0])
{
n = 1;
c[da + 1] = a[i][1];
if (c[da + 1] == c[0]) {//圈的输出
for (int j = 0; j < da + 1; j++)
cout << c[j] << ",";
cout << c[da + 1] << endl;
return n;
}
else n = circle(c, a, m, da + 1);
if (n) break;
}
return n;
}
int main(){
int n, m,dc, ac = 1, d = 0;
cout << "PLease input n,m:" << endl;
cin >> n >> m;
//输入并储存边
int(*A)[2] = new int[m][2];//储存有向边
int *B = new int[n];//储存没有进入边的结点
int *C = new int[n];//储存所有节点
int *D = new int[n+1];//或储存圈
for (int i = 0; i < m; i++)
cin >> A[i][0] >> A[i][1];
for (int i = 0; i < n; i++)
C[i] = i+1;
while (ac){
int bc = 0, i;
dc = d;
for (i = 0; i < n; i++){
if (C[i]){
int b = 1;
for (int j = 0; j < m;j++)
if (A[j][1] == i + 1) b = 0;//判断其结点是否有进入边
if (b){
B[d] = i + 1; d = d + 1; C[i] = 0;
for (int ij = 0; ij < m; ij++)
if (A[ij][0] == i + 1) A[ij][1] = 0;
}
}
}
if (dc == d) //一次遍历没有找到没有进入边的节点,就说明不是DAG,d是没有进入边节点个数减1
break;
else {
for (int a = 0; a < n; a++)
if (C[a] != 0) bc = 1;
if (!bc) ac = 0;
}
}
if (ac) {//圈的处理
cout << "NO" << endl;
for (int i = 0; i < n; i++)//初始化
D[i] = 0;
for (int i = 0; i < n; i++)
if (C[i]){
D[0] = C[i];
if (circle(D, A, m, 0)) break;
}
}
else{
cout << "YES" << endl;
for (int i = 0; i < n; i++)//输出拓扑序
{
if (i == n - 1) cout << B[i] << endl;
else cout << B[i] << ",";
}
}
return 0;
}


来自Android客户端1楼2016-11-07 14:57回复
    求大神啊


    来自Android客户端2楼2016-11-07 15:00
    回复