그래프 크기 구하기

<트리에서 단 한번의 dfs로 모든 정점들의 subtree 크기 구하기>

 

int sz[MAX]; //따로 초기화 해둘 필요 없음
bool vst[MAX];
void dfs(int curr) {
	vst[curr] = true;
	sz[curr] = 1;

	for (int next : adj[curr]) {
		if (!vst[next]) {
			dfs(next); //빠져나오면 curr의 next방향 서브트리의 sz모두 초기화
			sz[curr] += sz[next];
		}
	}
}

 

* 메인함수에서 dfs(rootNode)로 수행해야 모든 정점에 대해 구할 수 있음

 

* 양방향/단방향(부모->자식) 간선을 사용한 트리 모두에 대해 사용 가능

---

<양방향 그래프에서 컴포넌트 크기를 반환>

bool vst[MAX];
int dfs(int curr){
    vst[curr]=true;
    int ccnt=1;
    for(int next: adj[curr]){
    	if(!vst[next]) ccnt+=dfs(next);
    }
    return ccnt;
}