[C++] 2606 - 바이러스

문제 링크 : https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

 

알고리즘 분류에서 플로이드 와샬 알고리즘이 써있는데

사실 플로이드 와샬 알고리즘은 각 정점에서 모든 정점까지의 최단 경로를 구하는 걸로 알고있는데?)... ( 그래프는 아직 자세히 공부를 안함 )

사실 이 문제는 최단 경로를 구한다기 보다는 각 정점에서 도달 할 수 있는 모든 정점을 수를 구하는 것과 같기 때문에 그냥 BFS로 풀었다.

 

#include<bits/stdc++.h>
 
using namespace std;
 
#define endl '\n'
 
int G[105][105];
int visited[105];
int T, N;
int cnt;
queue<int> q;
 
void BFS(int v)
{
    int p;
    q.push(v);
    visited[v] = 1;
    while(!q.empty())
    {
        p = q.front();
        q.pop();
        cnt++;
        for(int i = 1; i <= N; ++i)
        {
            if(visited[i] == 0 && G[p][i] == 1)
            {
                q.push(i);
                visited[i] = 1;
            }
 
        }
    }
 
}
 
int main(void)
{
    cin >> N;
    cin >> T;
    int v1, v2;
    for(int i =0; i < T; ++i)
    {
        cin >> v1 >> v2;
        G[v1][v2] = G[v2][v1] = 1;
    }
 
    BFS(1);
 
    cout << cnt-1 << endl;
 
    return 0;
}