[c++] 백준 4195 - 친구 네트워크

0. [c++] 백준

https://www.acmicpc.net/problem/4195

1. 풀이

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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

#include<iostream> #include<vector> #include<algorithm> #include<queue> #include<string> #include<map>   using namespace std;   const int INF = 1000000007; int N; int arr[200001]; int set_size[200001];   int find(const int& x) {     if (x == arr[x])         return x;     else         return arr[x] = find(arr[x]); }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       int T;     cin >> T;       while (T--) {         cin >> N;           // 초기화를 해준다.         for (int i = 0; i <= N * 2; i++) {             arr[i] = i;             set_size[i] = 1;         }           map<string, int> name;         int idx = 1;         string a, b;           for (int i = 0; i < N; i++) {             cin >> a >> b;                          if (name.count(a) == 0)                 name[a] = idx++;             if (name.count(b) == 0)                 name[b] = idx++;               int aa = find(name[a]);             int bb = find(name[b]);               if (aa > bb) {                 arr[aa] = bb;                 set_size[bb] += set_size[aa];                 set_size[aa] = 0;                 cout << set_size[bb] << "\n";             }             else if(aa < bb) {                 arr[bb] = aa;                 set_size[aa] += set_size[bb];                 set_size[bb] = 0;                 cout << set_size[aa] << "\n";             }             else                 cout << set_size[aa] << "\n";         }     }       return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!