0

我正在尝试将图中的循环替换为一组顶点（删除此循环并放置一次具有最大数量的顶点）

struct group {
    int master; // representative of cycle
};

struct vertex {
    int *to; // neighbor list

    int nb; // how many neighbor
    int p; // parent
    short v; // was visited? 0 = false, 1 = true

    struct group *cycle; // is part of cycle? NULL = no, else pointer to group
};

我在每个顶点上运行 dfs

void searchCycles() {
    int i;
    for (i = 0; i < MAX_VER; i += 1)
        if (ver[i].v == 0 && ver[i].nb > 0)
            dfs(i);
}

dfs:

void dfs(int v) {
    ver[v].v = 1;

    int i;
    for (i = 0; i < ver[v].nb; i += 1) {
        ver[ver[v].to[i]].p = v;

        if (ver[ver[v].to[i]].v == 0)
            dfs(ver[v].to[i]);
        else
                    // cycle found
            replaceCycle(ver[v].to[i]);
    }
}

并替换函数喊打印循环中的顶点

void replaceCycle(int v) {
    struct group *g = &gr[usedGroup++];
    g->master = -1;

    printf("\nCYKL: %d ", v);

    int p = ver[v].p;

    while (p != v) {
        printf("%d(%d) ", p, v);

        p = ver[p].p;
    }

    printf("\n");
}

通常它是有效的，但有时它会出现无限循环。我尝试调试它，如果有两个或更多循环，父母（顶点结构中的 p）丢失，这意味着它工作正常但数字错误。我正在学习C和算法，所以我不太了解。

这不是家庭作业，这是一个 spoj 问题

4

1 回答 1

1

更换循环后，重新启动 dfs。

基本上，visited 标志可能会为您的第一个周期设置，但您希望将其清除以测试您的第二个周期。（以及第三，第四等）

于 2012-05-02T18:16:06.617 回答