오늘 푼 문제

https://www.acmicpc.net/problem/2606

바이러스

• 풀이 방식

컴퓨터의 수: 노드
컴퓨터 쌍의 수: 엣지

흔히 있는 미로 탐색, 최단 거리가 아닌 노드에서 노드로 이동하는 경우이므로 엣지로 연결되어있는 노드로 이동하는 수만 계산하면 된다.

나의 풀이

#include <iostream>
#include <vector>

using namespace std;

vector<int> v[101];
bool visit[101];

int cnt = 0;

void dfs(int x) {
	visit[x] = true;

	for (int i = 0; i < v[x].size(); i++) {
		int y = v[x][i];

		if (!visit[y]) {
			dfs(y);
			cnt++;
		}
	}
}

int main() {

	int N, M;
	int a, b;

	cin >> N;
	cin >> M;

	for (int i = 0; i < M; i++) {
		cin >> a;
		cin >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	dfs(1);

	cout << cnt << endl;

	return 0;
}