[백준 4195] 친구 네트워크 (C++)

[백준 4195] 친구 네트워크 (C++)

#include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321 using namespace std; int N, M, F; int parent[200001]; map m; //현재에는 자기 자신이 root임 //루트 노드를 찾아주는 코드 int find(int a) { //a가 root임 if (parent[a] < 0) return a; //a가 root가 아닐때 return parent[a] = find(parent[a]); } void merge(int a, int b) { a = find(a); b = find(b); if (a == b)return; //small to large if (parent[a] > parent[b]) swap(a, b); parent[a] += parent[b]; parent[b] = a; } int main() { FASTIO; int T,cnt=1,tmp, out; string a, b; cin >> T; for (int k = 0; k < T; k++) { cin >> F; for (int i = 0; i < 200001; i++) parent[i] = -1; for (int f = 0; f < F; f++) { cin >> a >> b; if (m.find(a) == m.end()) { m.insert({ a,cnt }); cnt++; } if (m.find(b) == m.end()){ m.insert({ b,cnt }); cnt++; } merge(m.find(a)->second, m.find(b)->second); tmp = find(m.find(a)->second); out = (-1) * parent[tmp]; cout << out << "

"; } m.clear(); } }

Union Find 로 풀리는 문제이다.

이름이 string으로 주어지기 때문에 map을 사용해서 풀어야 한다.

그리고 친구 관계 수가 100000 개가 주어지기 때문에 parent 를 100001로 설정해서 두번 틀렸다.

친구 관계수가 100000개 라는것은 친구 수는 최대 200000명이 될 수 있기 때문에 200001로 설정해야만 한다.

from http://kerryfrog.tistory.com/37 by ccl(A) rewrite - 2021-09-26 18:00:27