2606 바이러스

#include <stdio.h>
#include <algorithm>
#include <vector>
 
using namespace std;
 
vector<vector<int> > dp;
vector<vector<int> > adj;
 
int INF = 1000000000;
 
int main() {
    int com, net;
    scanf("%d %d", &com, &net);
 
    adj.assign(com+1, vector<int>(com+1, 0));
    dp.assign(com + 1, vector<int>(com + 1, INF));
 
    while (net--) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        adj[a][b] = 1;
        adj[b][a] = 1;
        dp[a][b] = 1;
        dp[b][a] = 1;
    }
 
    for (int i = 1; i <= com; i++) {
        dp[i][i] = 0;
    }
    
    for (int k = 1; k <= com; k++) {
        for (int i = 1; i <= com; i++) {
            for (int j = 1; j <= com; j++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
    int rst = 0;
    for (int i = 1; i <= com; i++) {
        if (dp[1][i] != 0 && dp[1][i] != INF)
            rst++;
    }
 
    printf("%d", rst);
}