그래프 - 깊이 우선 검색을 사용하여 무향 그래프에서 도달 할 수없는 노드를 찾습니다.

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로 계산할 수 있습니다.

그러나이 코드는 '카운트'에 대한 참조가 인 이라는 오류를 보여줍니다. 무엇이 문제입니까? DFS 재귀 적 방법에서 실수를 했습니까? C++ 라이브러리에서

Answer 1

이 count 함수 템플릿이 - (#include <bits/stdc++.h> 지시어가 포함 된) algorithm 헤더에, 당신은 dfs 및 main 기능에 count 전에 ::를 추가하여 문제를 해결할 수 있습니다. 당신이 네임 스페이스를 오염시키지해야하는 이유

::count= ::count+1; 

및

cout<<n-::count;