[알고리즘] c++ cpp 바이러스

포인트

1. DFS 하고 BFS 를 동시에 이해를 할 수 있는 문제

2. DFS 하고 BFS 는 구조적으로 정형화된 부분이 있어서 반복적으로 어떤 형식으로 흘러가는지를 아는 것은 좋은 것 같다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

vector<int> map[101];
bool visited[101];
int cnt;

void bfs(int a) {
	queue<int> q;
	q.push(a);
	visited[a] = 1;
	int cnt = 0;

	while (!q.empty()) {
		int x = q.front();
		q.pop();

		for (auto ele : map[x]) {
			if (!visited[ele]) {
				q.push(ele);
				visited[ele] = 1;
				cnt += 1;
			}
		}
	}

	cout << cnt << '\n';
}

void dfs(int a) {
	visited[a] = 1;
	cnt += 1;
	for (auto ele : map[a]) {
		if (!visited[ele])
			dfs(ele);
	}
}

int main() {
	int n;
	cin >> n;
	int t;
	cin >> t;

	while (t--) {
		int a, b;
		cin >> a >> b;
		map[a].push_back(b);
		map[b].push_back(a);
	}

	bfs(1);
	memset (visited, 0, sizeof (visited));
	
	dfs(1);
	cout << cnt-1 << '\n';

	return 0;
}