백준 4195 친구 네트워크

문제 URL : https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

 

문제 접근법 :  string 을이용한 disjoint set문제입니다.

정수형이 아니기때문에 parent 인덱스를 string으로 사용해야하기 때문에

인덱스를 string을 사용할수 있는 자료구조는 hash_map =  unordered_map 이나 map 을 이용해서 풀수있지만

단순히 떠바른 알고리즘을 사용하기위해 저는 unordered_map을 이용했습니다.

서로다른 루트일때 합칠경우 해당루트의 갯수들을 더해서 계산결과를 내면되기때문에

골드2 문제라고 하기엔 좀 아닌듯한 문제였습니다. 생각보다 쉬워서

 

소스코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

//By 콩순이냉장고 #include <iostream> #include <string> #include <unordered_map> using namespace std; unordered_map<string,pair<string,int>> parent; string find(string idx) {     if (parent[idx].first == idx)         return idx;     return parent[idx].first = find(parent[idx].first); } int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     int test;     cin >> test;     while (test--)     {         int n;         cin >> n;         parent.clear();         for (int i = 0; i < n; i++)         {             string a, b;             cin >> a >> b;             if (!parent.count(a))                 parent[a] = { a, 1 };             if (!parent.count(b))                 parent[b] = { b, 1 };             a = find(a);             b = find(b);                      if (a != b)             {                 int cnt = parent[b].second;                 parent[b] = parent[a];                 parent[a].second += cnt;             }             cout << parent[a].second << "\n";         }     } } Colored by Color Scripter

cs

 

모르는점 혹은 궁금한점 혹은 무엇인가 오류가 있다면 언제든지 댓글을 이용해주시길 바랍니다.