[백준/C++] 2060 바이러스 (S3)

유형	난이도	완료일	링크	특이사항
그래프	실버3	23/03/26	https://www.acmicpc.net/problem/2606

 

내 코드

#include <iostream>

using namespace std;

int arr[99999];

int main(void)
{
	int n=0, m=0;
	
	cin >> n >> m;
	
	int cnt = 0;
	int uniform = 1;
	
	int v1=0, v2=0;
	
	arr[1]=1;
	
	for(int i= 0 ; i< m; i++)
	{
		
		cin >> v1 >> v2;
		
		if(arr[v1]==0 && arr[v2]==0) //둘 다 0일 때는 집합 갯수+1 
		{
			cnt++;
			uniform++;
			arr[v1] = uniform;
			arr[v2]  = uniform;
		}
		
		else
		{
			if(arr[v1]!=0 && arr[v2]!=0) // 둘 다 0이 아니고
			{
				if(arr[v1] == arr[v2]) //둘이 같을 때는 pass
					continue;
				
				if(arr[v1] < arr[v2])
				{
					cnt -- ;
					int temp = arr[v2];
					int goal = arr[v1];
					for(int j = 1; j<= n; j++)
					{
						if(arr[j] == temp)
							arr[j] = goal;
					}
				}
				else if(arr[v1] > arr[v2])
				{
					cnt --;
					int temp = arr[v1];
					int goal = arr[v2];
					for(int j =1; j<=n; j++)
					{
						if(arr[j] == temp)
							arr[j] = goal;
					}
				}
			}
			else if(arr[v1] == 0 && arr[v2]!= 0)
			{
				arr[v1] = arr[v2];
			}
			else if(arr[v1]!=0 && arr[v2]==0)
			{
				arr[v2] = arr[v1];
			}
			else
				continue;
		}
		
	}
	
	int newCount=-1;
	for(int i= 1; i<=n; i++)
	{
		if(arr[i]==1)
			newCount++;
	}
	
	
	cout << newCount;
}

11724 연결 요소의 개수와 아주 비슷했다. 하지만 연결 요소 개수를 구할 필요는 없고 1번과 같은 집합에 속하는 수의 개수(1은 제외)를 구하면 된다. 코드를 약간만 수정해서 통과할 수 있었다.

1번 집합에 속한 요소들의 개수를 출력하는데, 처음에 무조건 “1 5”와 같이 1과 다른 숫자가 주어진다는 보장이 없으므로 1을 1번 집합에 넣어두고 시작했다.