[코딩테스트C++] 바이러스

오늘의 문제

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

바이러스

접근법

• 전형적인 DFS를 사용해서 푸는 그래프문제

나의 풀이

#include <iostream>
#include <vector>
using namespace std;
int n, m;
const int MAX = 100;
vector<vector<int>> arr(MAX);
bool visit[MAX] = {false, };
int cnt = 0;
// 바이러스
void dfs(int in){
    visit[in] = true;
    for(int i=0;i<arr[in].size();i++){
        if(visit[arr[in][i]] == false){
            cnt++;
            dfs(arr[in][i]);
        }
    }
}

다른 풀이

#include <stdio.h>
int n, m, x, y;
int p[101];

int Find(int x) {
	if (p[x] == x) {
		return x;
	}

	return p[x] = Find(p[x]);
}
void Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	if(x != y) p[y] = x;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) p[i] = i;
	while (m-- > 0) {
		scanf("%d %d", &x, &y);
		Union(x, y);
	}

	int root = Find(1);
	int ans = 0;
	for (int i = 2; i <= n; i++) if (Find(i) == root) ans++;

	printf("%d", ans);

	return 0;
}

배울 점

• 어렵게 푸셨다.