백준 4195번 친구네트워크

Algorithm

백준 4195번 친구네트워크

이무쿤 2019. 8. 28. 16:59

문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

기존의 union find에서 추가된건 string을 기반으로 찾아야 한다는 점. 그래서 map을 써야한다. vector사용시 시간초과 발생 map은 map<key type ,value type> m ; 으로 m[key] = value 이다 m.count(key)하면 키에 속한 value값을 알 수 있음.

그리고 또하나 문제점은 시간초과 해결인데 cin, cout 시간 차이를 잡아줘야 하고 endl사용을 하면 안됨. "\n"로 고쳐야 돌아감.

#include <iostream>
#include <map>
#include <string>

using namespace std;

int size[100001];
int parent[100001];

int findparent(int node)
{

if(parent[node] == node)
{
return node;
}

parent[node] = findparent(parent[node]);
return parent[node];
}

void merge( int pos1 , int pos2)
{

int node1 = findparent(pos1);
int node2 = findparent(pos2);

    if(node1 != node2)
        {

if(size[node1] <= size[node2])
{

parent[node1] = parent[node2];
size[node2] += size[node1];
size[node1] = 0;

cout<<size[node2]<<endl;


}
else
{

parent[node2] = parent[node1];
size[node1] += size[node2];
size[node2] = 0;

cout<<size[node1]<<endl;

}

   }
   else{

    cout<<size[node1] <<endl;

   }

}

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

        cin.tie(0);
int N, M;

cin >> N  ;

for(int i=0; i<N; i++)
{

cin >> M;
map<string, int> m;
        int index = 0;


        for(int i=0; i<=M; i++)
   {
parent[i] = i;
size[i] = 1;
   }

for(int j = 0; j<M; j++)
{
string str1;
string str2;

cin >> str1 >> str2;

       if(m.count(str1) == 0)
       {
           m[str1] = index++;
   }

   if(m.count(str2) == 0)
   {
      m[str2] = index++;
   }

    merge(m[str1],m[str2]);

}

}

}