친구 관계가 추가될 때마다 그룹에 몇 명이 있는지 출력해야 하기 때문에 그룹에 몇 명이 있는지 탐색하는 과정을 F번 반복해야 한다.
일일이 다 친구들과의 관계를 탐색하는 식으로 하면 시간 복잡도가 최소 F제곱이어서 불가능하다.
union-find 알고리즘을 쓰면 이를 해결할 수 있다.
#include<stdio.h>
#include<map>
#include<string>
using namespace std;
map<string, int> friends;
int group[300004];
int gsize[300004];
int fin(int x)
{
if(x==group[x]) return x;
return fin(group[x]);
}
int uni(int a, int b)
{
int ga = fin(a);
int gb = fin(b);
if(ga != gb){
group[ga] = group[gb];
gsize[gb] += gsize[ga];
return gsize[gb];
}
return gsize[ga];
}
int main()
{
int T;
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
int F;
int numfriend = 0;
friends = {};
scanf("%d",&F);
for(int j=1;j<=F;j++)
{
char a[100],b[100];
scanf("%s %s",a,b);
if(friends.find(a)==friends.end()){
numfriend++;
friends[a] = numfriend;
group[numfriend] = numfriend;
gsize[numfriend] = 1;
}
if(friends.find(b)==friends.end()){
numfriend++;
friends[b] = numfriend;
group[numfriend] = numfriend;
gsize[numfriend] = 1;
}
printf("%d\n",uni(friends[a], friends[b]));
}
}
}해결 코드이다.
일단 입력값이 문자열로 나오기 때문에 map을 이용할 것이다.
테스트 케이스 개수가 T이고, 반복될 때마다 map을 초기화 시켜준다.
입력을 받아서 a,b가 없다면 numfriend를 증가시키고 group과 size를 지정해준다.
그리고 uni 함수로 그룹을 합치고 합쳐진 그룹의 size를 리턴 받아서 출력하는 구조이다.
union-find 알고리즘만 구현하면 금방 풀 수 있는 문제였다.
