如何用深度优先搜索来计算无向图中每个连通部分的边数?

Question

对于一个无向图，给定数k和h，用dfs检查是否有任何连通分量有超过k条边，如果我们有超过h个连通分量。如果这两种情况之一为真，则返回false。我的解决方法正确吗?注意，对于这个练习，我不需要前任变量和时间变量，但为了清楚起见，我把它们留下了。我主要关心的是count变量。

    DFS(G)
    for each vertex u in G.V
        u.color = WHITE
        u.predecessor = NIL
    time = 0
    n = 0; //counts connected components
    for each vertex u in G.V
       if u.color == WHITE
            n = n + 1
            count = 0  // assign 0 initially for every connected component
            DFS-VISIT(G,U)
            if ((count + |Adj[u]|)/2 > k) 
                    return false;
    if (n > h) 
           return false;

   DFS-VISIT(G,u)
    time = time + 1 // white vertex u has just been discovered
    u.d = time      //u discovery time
    u.color = GRAY
    for each v in G.Adj[u]  // explore edge (u,v) 
         if v.color == WHITE
              count = count + |Adj[v]| //all edges are white only once.Sum of all adj lists for every vertice  gives 2|E|                       
              v.predecessor = u
              DFS-VISIT(G,v)
    u.color = BLACK // blacken u; it is finished
    time = time + 1
    u.f = time      //u finishing time

Answer 1

我想这样做可以

初始化col[]为1和2->未完成和0->完成

void dfs(long int i,list<long int> *edge,bool visited[],int col[],long int par[]){
    visited[i]=true;
    col[i]=2;
    list<long int>::iterator k;
    for(k=edge[i].begin();k!=edge[i].end();k++){
        int u=*k;
        if(col[u]==1){
            par[u]=i;
            e++;
            dfs(u,edge,visited,col,par);
        }
        else if(col[u]==2&&u!=par[i])
            e++;
    }
    col[i]=0;
}