使用c编程语言计算强连通分量

Question

对这段代码感到困惑所以这两个函数我认为是错误的

void dfsloop1(int **g)
{
    int i;
    int temp=0;
    for(i=0;i<875714;i++)
    {
        temp = f[i];
        x[temp-1] = i;
    }
    for(i=875714;i>0;i--)
    {
        if(!explored[x[i-1]])
        {
            s = i-1;
            dfs1(g,x[i-1]);
        }
    }
}

void dfs1(int **g,int i)
{

    explored[i] = 1;
    leader[i] = s;
    int j;
    for(j=0;j<a[i];j++)
    {
        if(!explored[(g[i][j]-1)])
        {
            dfs1(g,g[i][j]);
        }
    }
}

这里探索的数组正在考虑 node/vertex 是否被检查如果它被检查然后说第 ith 个顶点被检查 then explored[i-1] = 1 else explored[i-1] = 0,a[i] 存储有多少顶点 i+1 th 顶点被连接例如，顶点 1 与 2、4、5 相连，然后 a[0] 将是 3，图在邻接表中传递，我已经在反向图上有运行 dfs 并将那个神奇的编号存储在f[我] 使用 kosaraju 的算法，现在我正在尝试运行在我的原始图 g 上进行 dfs 在 x[i] 我正在按递增顺序存储 f[i] 例如让我们说 9 顶点图 f[0] = 7,f[1] = 3,f[2] = 1,f[4] = 2,f[5] = 5,f[6] = 9,f[7]=4,f[8] = 6 then x[0] = 2（这是最小的索引 f[i]),x[1] = 4,x[2] = 1 等等。

如果我遗漏了什么或不清楚的地方请告诉我。谢谢

顶点总数为875714

我是 Whosebug 的新手，所以如果我做错了什么请告诉我

谢谢

Answer 1

我查看了你的代码。我假设您是新手，因为您的主要功能与实际上并不方便的代码混杂在一起。
两件事：
1. 你正在处理指针和指针的指针。
2. 您正在为本地 variable/pointer.

消耗超过 10^5 个整数内存

我对指针了解不多。但是，作为一名参赛者，我曾经在本地声明巨大的数组时有 "Runtime Error"。所以，我认为你的问题出在这两个部分。尝试全局声明指针的指针。看看有没有帮助。

我给你一个link的SCC算法
e-maxx：https://e-maxx-eng.appspot.com/graph/strongly-connected-components.html

和我对 scc 的实现：
https://bitbucket.org/techboy_zero/programming-and-software-development/src/035560584ce7ab7e0a3f6ab5ae1406095bd39b62/Programming%20Contest%20Algorithms/Graph%20Theory/Strongly_Connected_Component.cpp

不过，我的是用 C++ 编写的。只需查看 dfs 和 kosaraju 函数即可。如果您在理解关键字方面有任何问题，请在 cplusplus.com 中搜索。如果不明白机制可以随时问我。

使用c编程语言计算强连通分量

Computing Strongly connected components using c programming language

c

algorithm

graph-algorithm