감염된 컴퓨터수 구하기

입력

7    //컴퓨터 개수

6    //앞으로입력할 네트웤연결횟수

1 2  //1,2번 컴퓨텨 연결되어있음

2 3

1 5

5 2

5 6

4 7

출력

5       //5대의 컴퓨터감염

조건

컴터 100대 이하

컴퓨터는 각각 1번부터 입력됨

번호쌍은 네트웤 직접연결되어있는 컴터번호

1번컴퓨터감염

총감염 컴퓨터수 출력

#include <stdio.h>

int main() {

    // 감염된 컴퓨터의 수를 구하기 위한 배열

    int infected[101]={0,};

    // 네트워크 연결을 위한 배열

    int connect[1000][2]={0,};

    // ncom은 컴퓨터의 댓수, nnet는 연결의 갯수

    int ncom, nnet, i, j;

    // src는 출발컴퓨터, dst도착컴퓨터, ninf감염된 컴퓨터댓수

    int src, dst, ninf=0;

    // 컴퓨터댓수를 입력

    scanf("%d", &ncom);

    // 연결의 갯수입력

    scanf("%d", &nnet);

    // 연결을 읽어서 connect배열에 저장

    for(i=0;i<nnet;i+=1) {

        scanf("%d%d", &connect[i][0], &connect[i][1]);

    }

    // 1번 컴퓨터가 감염이라고 넣음

    infected[1]=1;

    // 연결이 계속되어 끝까지 갈 수 있는 최대 길이는 ncom만큼이다.

    for(i=0;i<ncom;i+=1) {

        // 모든 연결에 대해서 현재 감염된 컴퓨터가 src이면, dst를 감염시킨다.

        for(j=0;j<nnet;j+=1) {

            src=connect[j][0];    // src

            dst=connect[j][1];    // dst

            // 만약 src가 감염되었으면 dst를 감염시킨다.

            if(infected[src]!=0) { infected[dst]=1; }

        }

    }

    // 1부터 ncom까지 가면서 감염된 컴퓨터의 댓수를 누적한다.

    for(i=1;i<=ncom;i+=1) {

        if(infected[i]!=0) { ninf+=1; }

    }

    printf("%d", ninf);

    return 0;

}