백준 2026번 바이러스

 

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

 

 

간단한 union Find 문제 .

 

 

 

 

 

 

 

 

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

int N,E;
int parent[101], setSize[101];





int findparent(int node) 
{ 
if(node==parent[node]) 
 return node; 
  
  
 
    //재귀만 사용해서 정말 찾는 용도로만 쓸 수 있지만 parent를 업데이트 시키지 않으면 시간복잡도가 증가. 매번 집합의 길이 만큼 탐색해야 하므로 2단계 트리로 구성하기 위해 업뎃함. 
  return parent[node]==findparent(parent[node]);  
  
 



} 

void merge(int node1, int node2)
{

        node1 = findparent(node1); //node1이 속한 집합을 찾음

        node2 = findparent(node2); //node2가 속한 집합을 찾음

                                                             //같은 집합이 아닐 경우에만 합친다

        if (node1 != node2)

        {

                 //크기가 더 큰 집합으로 작은 집합이 들어감

                 if (setSize[node1] < setSize[node2])

                         swap(node1, node2);

 

                 parent[node2] = node1; //node2 집합이 node1에 합쳐짐

                 setSize[node1] += setSize[node2]; //node1의 집합 크기가 커짐

                 setSize[node2] = 0; //node2가 node1에 흡수되므로

        }

}

 

int main(void)
{
ios_base::sync_with_stdio(0);

        cin.tie(0);



cin >> N >>E;

for(int i=1; i<=N; i++)
 {
 parent[i]=i;
 setSize[i]=1;
     }


for(int i=0; i<E; i++)
{
int temp1, temp2;

cin >> temp1 >> temp2;

merge(temp1,temp2);

}


cout << setSize[parent[1]]-1 <<endl;

return 0;



}