[백준/BOJ] 백준 2606번 : 바이러스

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

2606번: 바이러스

플로이드 알고리즘을 이용해 정점 간에 도달할 수 있는지 구하고, 0번 컴퓨터(0번 컴퓨터부터 있다고 설정)를 제외한 나머지 컴퓨터중에 0번 컴퓨터에서 도달할 수 있는 것의 개수를 센다.

 

코드

#include <iostream>
#include <cstring>
using namespace std;

int adj[100][100];
int n, num;

//플로이드 알고리즘을 이용해 정점간에 도달할 수 있는지 구한다
void Solve()
{
	for (int i = 0; i < n; i++)
		adj[i][i] = 1;

	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				adj[i][j] = adj[i][j] || (adj[i][k] && adj[k][j]);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int temp1, temp2;
	int result = 0;
	
	memset(adj, 0, sizeof(adj));

	cin >> n >> num;

	//직접 연결되어 있는 쌍을 입력받는다
	for (int i = 0; i < num; i++)
	{
		cin >> temp1 >> temp2;

		//0번 컴퓨터부터 시작한다고 하고, temp1과 temp2에 -1을 한다
		adj[temp1-1][temp2-1] = 1;
		adj[temp2-1][temp1-1] = 1;
	}

	Solve();

	//0번 컴퓨터를 제외한 나머지 컴퓨터중에 0번 컴퓨터에서 도달 할 수 있는것의 개수를 센다
	for (int i = 1; i < n; i++)
	{
		if (adj[0][i] == 1)
			result++;
	}

	cout << result;

	return 0;
}