使用深度优先搜索在无向图中查找不可达节点

Question

我有一个无向图（可能是断开连接的图）。我需要找到给定节点的无法访问的节点数。

#include<bits/stdc++.h>
using namespace std;
vector<int> graph[1000];
bool visited[1000];
int count=0;

void dfs(int s)
{
  count=count+1;
  visited[s]=true;
  for(int i=0;i<graph[s].size();i++)
    if(visited[graph[s][i]]==false)
      dfs(i);
}

int main()
{
  int n,m;
  cin>>n>>m;
  int i;
  for(i=0;i<m;i++)
  {
    int x,y; 
    cin>>x>>y;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }
  int k;
  cin>>k;
  dfs(k);

  cout<<n-count;
}

最初该图有 n 个节点。在 DFS 过程之后，对于特定节点 k ，dfs(k) 找到与 k 连接的节点数。所以不可达节点可以通过n-count来计算。

但是此代码显示一个错误，指出 对 'count' 的引用不明确 。问题是什么？我是不是在DFS递归方法上搞错了？

Answer 1

在 C++ 库中有 count 函数模板 - 在 algorithm header 中（包含在 #include <bits/stdc++.h> 指令中），您可以通过添加 :: 在 dfs 和 main 函数中的 count 之前。

  ::count= ::count+1;

和

  cout<<n-::count;

使用深度优先搜索在无向图中查找不可达节点

Graph-Finding unreachable nodes in undirected graph using Depth First Search

c++

graph

depth-first-search