[백준] 2606 바이러스

문제 출처: www.acmicpc.net/problem/2606

2606번: 바이러스

: 1번에 연결되면 바이러스에 걸린다고 할 때 웜 바이러스에 걸리게 되는 컴퓨터의 수를 계산해야 한다.

: uion-find 알고리즘을 사용해서 만약 부모가 다르면 작은 쪽을 넣어주게 한다.

: 최종적으로 1이 부모인 경우는 모두 1을 부모로 가지고 있기 때문에 부모 배열을 순회하면서 1이 개수를 계산한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N;
	static int[] p;
	static void make() {
		for(int i = 1; i < N+1; i++) {
			p[i] = i;
		}
	}
	static int find(int idx) {
		if(p[idx] == idx) return idx;
		return p[idx] = find(p[idx]);
	}
	static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		if(aRoot == bRoot) return false;
		if(aRoot < bRoot)p[bRoot] = aRoot;
		else p[aRoot] = bRoot;
		return true;
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		N = Integer.parseInt(br.readLine()); // 컴퓨터 개수
		p = new int[N+1];
		make();
		int M = Integer.parseInt(br.readLine());
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			union(a,b);
		}
		int cnt = 0;
		for(int i = 2; i < N+1; i++) {
			find(i);
			if(p[i] == 1) cnt++;
		}
//		System.out.println(Arrays.toString(p));
		System.out.println(cnt);
	}
}