c++ - DFS - 检查周期

Question

目标是找出无向、未加权的图是否是树，即检查它是否包含后边。我正在使用一种修改形式的白-灰-黑 DFS 算法(在 Cormen 和此处提到的注释中给出:http://www.cs.cornell.edu/~wdtseng/icpc/notes/graph_part1.pdf)

但不知何故，它不起作用。它工作了一次，但在 SPOJ ( http://www.spoj.com/problems/PT07Y/ ) 导致了运行时错误。

更新:我现在得到了这个问题的错误答案。不过，该代码适用于示例测试用例。

失败的测试用例:

10 9

1 2

2 3

3 4

4 5

5 6

6 4

6 7

7 8

8 9

---

#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <vector>
#include <cstdlib>
using namespace std;

bool  M[10001][10001] = { 0 } ;
int color[10001] = { 0  };
long long int n;
bool answer=false;
void condition()
{
    cout<<"NO"<<endl;
    exit(0);
}
void condition2()
{
    cout<<"YES"<<endl;
    exit(0);
}

void dfs(int u, int p)
{
    color[u] = 1;
    for(int v=0; v < n; v++)
        {
            if(M[u][v] && v != p)
                {
                    if (color[v] == 0)
                        dfs(v, u);
                    else if (color[v]==1)
                    {
                         condition(); /* It has a backedge so it is not a tree, so print No */
                    }
                }
        }

    condition2(); /* It does not have backedge so it is not a tree so print YES */


}

int main()
{


long Z;
cin>>n>>Z;


// for(int i=0; i<n; i++) /* **Removed THIS nested loop to reduce runtime, successfully eliminated TLE** */
//     for(int j=0; j<n;j++)
//        M[i][j]=0;

for(int i=0; i < Z; i++)
{
    long temp1, temp2;
    cin>>temp1;
    cin>>temp2;
    temp1--;
    temp2--;

    M[temp1][temp2]=1;
    M[temp2][temp1]=1;

}


if(Z==n-1)
    dfs(0, -1);
else cout<<"NO"<<endl;

return 0;
}

Answer 1

如果图是连通的且E = V-1，则它是一棵树，其中E 和V 是边数和节点分别。因此，只要在启动 DFS 之前检查 E==V-1，您应该能够在 O(V) 时间内解决它。

你能否针对一个图测试你的程序，该图是一条具有 20000 个节点的路径，节点编号为 0 是一片叶子，并且有一条来自 的边i 到 i+1？请尝试将堆栈大小限制设置为 SPOJ(8MB IIRC) 上的限制来运行它，并确保您没有堆栈溢出。这是堆栈使用情况的最坏情况图。如果确实发现递归太深，则可以使用 BFS 来检查连通分量的数量是否为 1。或者，您可以使用 path compression ，这将使您的运行时间 O(n log n)，但仍然足够快以适应 1 秒的限制。